Bounds for the D0L language equivalence problem

DOI10.1016/j.ic.2003.12.002zbMath1101.68658OpenAlexW2063594250MaRDI QIDQ598185

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

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

Related Items (2)

A new bound for the D0L language equivalence problem ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On a bound for the DOL sequence equivalence problem
• Simple reductions between \(D0L\) language and sequence equivalence problems
• Elementary homomorphisms and a solution of the DOL sequence equivalence problem
• The equivalence problem of polynomially bounded D0L systems -- a bound depending only on the size of the alphabet
• A short solution for the HDT0L sequence equivalence problem
• On the equivalence problem for binary DOL systems
• The decidability of the equivalence problem for DOL-systems
• On the decidability of some equivalence problems for DOL-systems
• A polynomial bound for certain cases of the D0L sequence equivalence problem

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