Geodesic
On algorithmic properties of finite subset algebra for some unoids
Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 4 (2019), pp. 108-116 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider unoids consisting of identical non-branching trees which are connected into an infinite line. We establish that the finite subset algebra admits effective quantifier elimination and it does not depend on the original algebra. So, we have an instance where the finite subset algebra theory is algorithmically simpler than the theory of the original one. Also it demonstrates that the union operation for finite subset algebras does matter for algorithmical properties.
Mots-clés : unoid, quantifier elimination.
Keywords: non-branching tree, subset algebra 
@article{VTPMK_2019_4_a7,
     author = {S. M. Dudakov},
     title = {On algorithmic properties of finite subset algebra for some unoids},
     journal = {Vestnik Tverskogo gosudarstvennogo universiteta. Seri\^a Prikladna\^a matematika},
     pages = {108--116},
     year = {2019},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VTPMK_2019_4_a7/}
}
TY  - JOUR
AU  - S. M. Dudakov
TI  - On algorithmic properties of finite subset algebra for some unoids
JO  - Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
PY  - 2019
SP  - 108
EP  - 116
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/VTPMK_2019_4_a7/
LA  - ru
ID  - VTPMK_2019_4_a7
ER  - 
%0 Journal Article
%A S. M. Dudakov
%T On algorithmic properties of finite subset algebra for some unoids
%J Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
%D 2019
%P 108-116
%N 4
%U http://geodesic.mathdoc.fr/item/VTPMK_2019_4_a7/
%G ru
%F VTPMK_2019_4_a7
S. M. Dudakov. On algorithmic properties of finite subset algebra for some unoids. Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 4 (2019), pp. 108-116. http://geodesic.mathdoc.fr/item/VTPMK_2019_4_a7/

[1] Dudakov S. M., “On the unsolvability of the algebra of one-character languages with the operation of concatenation”, Conference proceedings “Algebra and Mathematical Logic: Theory and applications” (Kazan, 24-28 of June 2019), KFU, Kazan, 2019, 101–103 (in Russian)

[2] Karlov B. N., “On the theory of regular languages with an iteration operator”, Conference proceedings “Algebra and Mathematical Logic: Theory and applications” (Kazan, 24-28 of June 2019), KFU, Kazan, 2019, 114–115 (in Russian)

[3] Boolos G. S., Burgess J. P., Jeffrey R. C., Computability and Logic, 5th edition, Cambridge University Press, New York, 2007 | MR | Zbl

[4] Dudakov S. M., Karlov B. N., “On Decidability of Regular Languages Theories”, Proc. of 14th International Computer Science Symposium in Russia, CSR 2019, v. 11532, LNCS, 2019, 119–130 | MR | Zbl

[5] Rogers H., Theory of Recursive Functions and Effective Computability, McGraw-Hill Education, New York, 1967 | MR | Zbl