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.


68Q45 Formal languages and automata


Zbl 0575.00023