zbMATH — the first resource for mathematics

L morphisms: Bounded delay and regularity of ambiguity. (English) Zbl 0766.68078
Automata, languages and programming, Proc. 18th Int. Colloq., Madrid/Spain 1991, Lect. Notes Comput. Sci. 510, 566-574 (1991).
Summary: [For the entire collection see Zbl 0753.00027.]
We present characterization and decidability results concerning bounded delay of \(L\) codes. It is also shown that, for \(L\) morphisms (morphisms applied in the “\(L\) way”), the sets causing ambiguities are in most cases effectively regular. The results are closely linked with some fundamental issues (bounded dealy, elementary morphisms, defect theorem) in the theory of codes and combinatorics of words in general.

68Q45 Formal languages and automata
68R15 Combinatorics on words