The ω sequence problem for DOL systems is decidable

DOI10.1145/62.2161MaRDI QIDQ3769989zbMATH OpenOpenAlexFDO

Authors Karel II Culik, Tero Harju

Publication date 1984

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/62.2161

zbMATH Keywords

decidabilityhomomorphismsinfinite wordsD0L systemsparallel rewriting systems\(\omega \)-equivalencelimit language equivalence

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Recommendations

• THE D0L ω-EQUIVALENCE PROBLEM
• REMARKS CONCERNING THE D0L ω-EQUIVALENCE PROBLEM
• The sequence equivalence problem for primitive D0L systems
• scientific article; zbMATH DE number 4045201
• An \(n^2\)-bound for the ultimate equivalence problem of certain D0L systems over an \(n\)-letter alphabet

Cited in

(24)

• REMARKS CONCERNING THE D0L ω-EQUIVALENCE PROBLEM
• THE D0L ω-EQUIVALENCE PROBLEM
• Decidability of uniform recurrence of morphic sequences
• A bound for theω-equivalence problem of polynomial D0L systems
• Simple reductions between \(D0L\) language and sequence equivalence problems
• scientific article; zbMATH DE number 4045201 (Why is no real title available?)
• On the subword equivalence problem for morphic words
• On infinite words generated by polynomial D0L systems
• Towards a proof of the decidability of the momentary stagnation of the growth function of D0L systems
• The language equivalence problem for HD0L systems having D0L growths
• Iterative devices generating infinite words
• On D0L systems with immigration
• The equality problem for purely substitutive words
• The equality problem for infinite words generated by primitive morphisms
• scientific article; zbMATH DE number 3940748 (Why is no real title available?)
• scientific article; zbMATH DE number 3872709 (Why is no real title available?)
• Decidability of periodicity for infinite words
• On infinite HD0L words having sparse letters
• D0L sequence equivalence is inPfor fixed alphabets
• ON UNIFORMLY RECURRENT MORPHIC SEQUENCES
• scientific article; zbMATH DE number 3864525 (Why is no real title available?)
• HD0L \(\omega \)-equivalence and periodicity problems in the primitive case
• An \(n^2\)-bound for the ultimate equivalence problem of certain D0L systems over an \(n\)-letter alphabet
• scientific article; zbMATH DE number 4055075 (Why is no real title available?)

This page was built for publication: The ω sequence problem for DOL systems is decidable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3769989)