Geodesic
On the solution of automaton equations
Diskretnaya Matematika, Tome 16 (2004) no. 2, pp. 104-116 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider the problem of solving automata equations in one variable. We suggest an algorithm for determining whether a given equation has a solution. We introduce the notion of a boundedly non-determinate function. It is proved that if an automaton equation has a solution, then the set of all solutions of this equation is embedded into some boundedly non-determinate function which can be effectively constructed on the base of the initial equation. 
@article{DM_2004_16_2_a7,
     author = {I. V. Lyalin},
     title = {On the solution of automaton equations},
     journal = {Diskretnaya Matematika},
     pages = {104--116},
     year = {2004},
     volume = {16},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2004_16_2_a7/}
}
TY  - JOUR
AU  - I. V. Lyalin
TI  - On the solution of automaton equations
JO  - Diskretnaya Matematika
PY  - 2004
SP  - 104
EP  - 116
VL  - 16
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DM_2004_16_2_a7/
LA  - ru
ID  - DM_2004_16_2_a7
ER  - 
%0 Journal Article
%A I. V. Lyalin
%T On the solution of automaton equations
%J Diskretnaya Matematika
%D 2004
%P 104-116
%V 16
%N 2
%U http://geodesic.mathdoc.fr/item/DM_2004_16_2_a7/
%G ru
%F DM_2004_16_2_a7
I. V. Lyalin. On the solution of automaton equations. Diskretnaya Matematika, Tome 16 (2004) no. 2, pp. 104-116. http://geodesic.mathdoc.fr/item/DM_2004_16_2_a7/

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

[2] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Nauka, Moskva, 1979 | MR | Zbl

[3] Evtushenko N., Villa T., Petrenko A., Braiton R., Sandzhovanni–Vintsentelli A., Reshenie uravnenii v logicheskom sinteze, Spektr, Tomsk, 1999

[4] Trakhtenbrot B. A., Barzdin Ya. M., Konechnye avtomaty (povedenie i sintez), Izdatelstvo “Nauka”, Moskva, 1970 ; Трахтенброт Б. А., “Конечные автоматы и логика одноместных предикатов”, Сиб. матем. журнал, 3:1 (1962), 103–131 | MR