×

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.

MSC:

68Q45 Formal languages and automata
68R15 Combinatorics on words

Citations:

Zbl 0753.00027
PDF BibTeX XML Cite