Geodesic
Automata transformations of prefix decidable and decidable by Buchi superwords
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 7 (2016), pp. 55-65.

Voir la notice de l'article provenant de la source Math-Net.Ru

We show that the set of prefix decidable superwords is closed under finite automata and asynchronous automata transformations. We prove that structures of degrees of finite automata and asynchronous automata transformations contain an atom which consists of prefix decidable superwords with undecidable monadic theory (or undecidable by Buchi). Also we prove that the structure of degrees of asynchronous automata transformations contains an atom which consists of superwords with decidable monadic theory (decidable by Buchi).
Keywords: superword, prefix decidability, decidability by Buchi, monadic theory, degrees, atom.
Mots-clés : automata transformation 
@article{IVM_2016_7_a6,
     author = {N. N. Korneeva},
     title = {Automata transformations of prefix decidable and decidable by {Buchi} superwords},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {55--65},
     publisher = {mathdoc},
     number = {7},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2016_7_a6/}
}
TY  - JOUR
AU  - N. N. Korneeva
TI  - Automata transformations of prefix decidable and decidable by Buchi superwords
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2016
SP  - 55
EP  - 65
IS  - 7
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IVM_2016_7_a6/
LA  - ru
ID  - IVM_2016_7_a6
ER  - 
%0 Journal Article
%A N. N. Korneeva
%T Automata transformations of prefix decidable and decidable by Buchi superwords
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2016
%P 55-65
%N 7
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IVM_2016_7_a6/
%G ru
%F IVM_2016_7_a6
N. N. Korneeva. Automata transformations of prefix decidable and decidable by Buchi superwords. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 7 (2016), pp. 55-65. http://geodesic.mathdoc.fr/item/IVM_2016_7_a6/

[1] Semenov A. L., “Logicheskie teorii odnomestnykh funktsii na naturalnom ryade”, Izv. AN SSSR. Ser. matem., 47:3 (1983), 623–658 | MR | Zbl

[2] Muchnik An., Semenov A., Ushakov M., “Almost periodic sequences”, Theoret. Comput. Sci., 304 (2003), 1–33 | DOI | MR | Zbl

[3] Muchnik An. A., Pritykin Yu. L., Semenov A. L., “Posledovatelnosti, blizkie k periodicheskim”, UMN, 64:5 (2009), 21–96 | DOI | MR | Zbl

[4] Pritykin Yu. L., “Konechno-avtomatnye preobrazovaniya strogo pochti periodicheskikh posledovatelnostei”, Matem. zametki, 80:5 (2006), 751–756 | DOI | MR | Zbl

[5] Pritykin Yu. L., “Pochti periodichnost, konechno-avtomatnye preobrazovaniya i voprosy effektivnosti”, Izv. vuzov. Matem., 2010, no. 1, 74–87 | MR | Zbl

[6] Dekking F. M., “Iteration of maps by an automaton”, Discrete Math., 126:1–3 (1994), 81–86 | DOI | MR | Zbl

[7] Cobham A., “Uniform tag sequences”, Math. Systems Theory, 6:1–3 (1972), 164–192 | DOI | MR | Zbl

[8] Vyalyi M. N., Rubtsov A. A., “Algoritmicheskaya razreshimost zadach o povedenii avtomatov na sverkhslovakh”, Diskretn. analiz i issledov. operatsii, 19:2 (2012), 3–18 | MR | Zbl

[9] Buchi J. R., “On a decision method in restricted second order arithmetic”, Logic, Methodology and Philosophy of Sci., Proc. of Intern. Congr., Stanford Univ. Press, Stanford, CA, 1960, 1–11 | MR

[10] Kudryavtsev V. B., Aleshin S. V., Podkolzin A. S., Vvedenie v teoriyu avtomatov, Nauka, M., 1985 | MR

[11] Bairasheva V. R., Stepeni avtomatnykh preobrazovanii pochti periodicheskikh sverkhslov i sverkhslov s razreshimoi monadicheskoi teoriei, No 3103-V89, VINITI, Kazan, 1989

[12] Korneeva N. N., “Ob avtomatnykh preobrazovaniyakh i monadicheskikh teoriyakh beskonechnykh posledovatelnostei”, Izv. vuzov. Matem., 2011, no. 8, 90–93 | MR | Zbl

[13] Korneeva N. N., “Monadicheskie teorii posledovatelnostei pri asinkhronno avtomatnykh preobrazovaniyakh”, Uchen. zap. Kazansk. un-ta. Ser. Fiz.-matem. nauki, 154, no. 2, 2012, 117–124 | MR

[14] Reina G., “Stepeni avtomatnykh preobrazovanii”, Kiberneticheskii sb., 14, 1977, 95–106

[15] Korneeva N. N., “Stepeni asinkhronno avtomatnykh preobrazovanii”, Izv. vuzov. Matem., 2011, no. 3, 30–40 | MR | Zbl