Geodesic
On solutions to systems of automata-type functional equations
Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 4, pp. 86-98.

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

The automata-type functional equations are considered. These equations include subject variables for natural numbers and one-placed functional variables for infinite binary sequences. An algorithm is defined which solves the satisfiability problem for finite systems of functional equations containing only functions $1$ and $t+1$. The linear homogeneous structures are used to establish the lower bound for time complexity of similar deciding algorithms. It is proved that the satisfiability problem is algorithmically undecidable for the systems of functional equations which contain yet the functions $2t,3t$, and $5t$. Tab. 1, bibliogr. 10.
Keywords: automata-type functional equation, satisfiability problem. 
@article{DA_2012_19_4_a7,
     author = {S. S. Marchenkov},
     title = {On solutions to systems of automata-type functional equations},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {86--98},
     publisher = {mathdoc},
     volume = {19},
     number = {4},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2012_19_4_a7/}
}
TY  - JOUR
AU  - S. S. Marchenkov
TI  - On solutions to systems of automata-type functional equations
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2012
SP  - 86
EP  - 98
VL  - 19
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2012_19_4_a7/
LA  - ru
ID  - DA_2012_19_4_a7
ER  - 
%0 Journal Article
%A S. S. Marchenkov
%T On solutions to systems of automata-type functional equations
%J Diskretnyj analiz i issledovanie operacij
%D 2012
%P 86-98
%V 19
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2012_19_4_a7/
%G ru
%F DA_2012_19_4_a7
S. S. Marchenkov. On solutions to systems of automata-type functional equations. Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 4, pp. 86-98. http://geodesic.mathdoc.fr/item/DA_2012_19_4_a7/

[1] Byukhi D. R., “Slabaya arifmetika vtorogo poryadka i konechnye avtomaty”, Kibernet. sbornik, 8, Mir, M., 1964, 42–77

[2] Katerinochkina N. N., “Ob ekvivalentnosti nekotorykh vychislitelnykh ustroistv”, Kibernetika, 1970, no. 5, 27–31

[3] Kobrinskii N. E., Trakhtenbrot B. A., Vvedenie v teoriyu konechnykh avtomatov, Fizmatlit, M., 1962, 404 pp. | MR

[4] Kuroda S. I., “Klassy yazykov i lineino ogranichennye avtomaty”, Kibernet. sbornik, 9, Mir, M., 1972, 36–51

[5] Lyalin I. V., “O reshenii avtomatnykh uravnenii”, Diskret. matematika, 16:2 (2004), 104–116 | MR | Zbl

[6] Maltsev A. I., Algoritmy i rekursivnye funktsii, Nauka, M., 1986, 392 pp. | MR

[7] Marchenkov S. S., “O slozhnosti klassa $\mathcal E^2$ Gzhegorchika”, Diskret. matematika, 22:1 (2010), 5–16 | MR | Zbl

[8] Meier A. R., “Slabaya singulyarnaya teoriya vtorogo poryadka funktsii sledovaniya ne elementarno rekursivna”, Kibernet. sbornik, 12, Mir, M., 1975, 62–77

[9] Minskii M., Vychisleniya i avtomaty, Mir, M., 1971, 364 pp. | MR

[10] Trakhtenbrot B. A., Barzdin Ya. M., Konechnye avtomaty. Povedenie i sintez, Nauka, M., 1970, 400 pp. | MR | Zbl