On solving automaton equations
I. V. Lyalin · Discrete Mathematics and Applications · 2004
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.