Bounds for the D0L language equivalence problem

DOI10.1016/J.IC.2003.12.002MaRDI QIDQ598185zbMATH OpenOpenAlexFDO

Authors Juha Honkala

Publication date 6 August 2004

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2003.12.002

zbMATH Keywords

D0L systemsDecidabilityEquivalence problem

Mathematics Subject Classification ID

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

Recommendations

• A polynomial bound for certain cases of the D0L sequence equivalence problem
• A new bound for the D0L language equivalence problem
• An \(n^2\)-bound for the ultimate equivalence problem of certain D0L systems over an \(n\)-letter alphabet
• A new bound for the D0L sequence equivalence problem
• Bounded D0L languages

Cites work

• A polynomial bound for certain cases of the D0L sequence equivalence problem
• A short solution for the HDT0L sequence equivalence problem
• Elementary homomorphisms and a solution of the DOL sequence equivalence problem
• scientific article; zbMATH DE number 3940751 (Why is no real title available?)
• scientific article; zbMATH DE number 3990879 (Why is no real title available?)
• scientific article; zbMATH DE number 3569855 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• On a bound for the DOL sequence equivalence problem
• On the decidability of some equivalence problems for DOL-systems
• On the equivalence problem for binary DOL systems
• Simple reductions between D0L language and sequence equivalence problems
• The decidability of the equivalence problem for DOL-systems
• The equivalence problem of polynomially bounded D0L systems -- a bound depending only on the size of the alphabet

Cited in

(14)

• Bounded D0L languages
• Simple reductions between D0L language and sequence equivalence problems
• A new bound for the D0L language equivalence problem
• The language equivalence problem for HD0L systems having D0L growths
• An \(n^2\)-bound for the ultimate equivalence problem of certain D0L systems over an \(n\)-letter alphabet
• scientific article; zbMATH DE number 1819637 (Why is no real title available?)
• scientific article; zbMATH DE number 3972218 (Why is no real title available?)
• scientific article; zbMATH DE number 4028926 (Why is no real title available?)
• scientific article; zbMATH DE number 58306 (Why is no real title available?)
• scientific article; zbMATH DE number 1361492 (Why is no real title available?)
• A characterization of morphic words with polynomial growth
• The equivalence problem for languages defined by transductions on D0L languages
• On infinite words generated by polynomial D0L systems
• A new bound for the D0L sequence equivalence problem

This page was built for publication: Bounds for the D0L language equivalence problem

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