Fixed and stationary $$\omega$$-words and $$\omega$$-languages.(English)Zbl 0586.68063

The book of L, dedic. A. Lindenmayer Occas. 60th Birthday, 147-156 (1986).
[For the entire collection see Zbl 0575.00023.]
Explicit representations of the $$\omega$$-words that are fixed (resp., stationary) relative to a function $$h: A\to A^*$$ are given. A procedure is provided for constructing a concise expression for the fixed (resp., stationary) $$\omega$$-language of such an h. The equivalence problem for fixed (resp., stationary) $$\omega$$-languages of functions h&k: $$A\to A^*$$ is shown to be decidable. The fundamental tool for this latter procedure is the recently developed algorithm of K. Culik II and T. Harju [J. Assoc. Comput. Mach. 31, 282-298 (1984)] for deciding the $$\omega$$-sequence equivalence problem.

MSC:

 68Q45 Formal languages and automata

Zbl 0575.00023