RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2004 Volume 16, Issue 2, Pages 104–116 (Mi dm156)

This article is cited in 2 papers

On the solution of automaton equations

I. V. Lyalin


Abstract: 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.

UDC: 519.7

Received: 10.11.2003

DOI: 10.4213/dm156


 English version:
Discrete Mathematics and Applications, 2004, 14:3, 287–300

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024