On a bound for the DOL sequence equivalence problem

DOI10.1016/0304-3975(80)90064-XzbMath0456.68085OpenAlexW2008201565MaRDI QIDQ1151051

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Publication date: 1980

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(80)90064-x

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

A new bound for the D0L sequence equivalence problem ⋮ Bounds for the D0L language equivalence problem ⋮ D0L sequence equivalence is inPfor fixed alphabets ⋮ Explicit test sets for iterated morphisms in free monoids and metabelian groups ⋮ Easy cases of the D0L sequence equivalence problem ⋮ An \(n^2\)-bound for the ultimate equivalence problem of certain D0L systems over an \(n\)-letter alphabet

Cites Work

• Elementary homomorphisms and a solution of the DOL sequence equivalence problem
• The decidability of the equivalence problem for DOL-systems