The language equivalence problem for HD0L systems having D0L growths

DOI10.1016/J.TCS.2004.09.014MaRDI QIDQ1763705zbMATH OpenOpenAlexFDO

Authors Juha Honkala

Publication date 22 February 2005

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

Full work available at URL https://doi.org/10.1016/j.tcs.2004.09.014

zbMATH Keywords

D0L systemHD0L systemLanguage equivalence problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• A new bound for the D0L language equivalence problem
• scientific article; zbMATH DE number 2016846
• The ω sequence problem for DOL systems is decidable
• Bounds for the D0L language equivalence problem
• An \(n^2\)-bound for the ultimate equivalence problem of certain D0L systems over an \(n\)-letter alphabet

Cites work

• scientific article; zbMATH DE number 5604086 (Why is no real title available?)
• 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 3668002 (Why is no real title available?)
• scientific article; zbMATH DE number 3746452 (Why is no real title available?)
• scientific article; zbMATH DE number 41838 (Why is no real title available?)
• scientific article; zbMATH DE number 3569855 (Why is no real title available?)
• scientific article; zbMATH DE number 3588051 (Why is no real title available?)
• scientific article; zbMATH DE number 2016846 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• A short solution for the HDT0L sequence equivalence problem
• Elementary homomorphisms and a solution of the DOL sequence equivalence problem
• On sentential forms of context-free grammars
• On the Images of ℕ-Rational Sequences Counting Multiplicities
• On the decidability of some equivalence problems for DOL-systems
• On the decidability of the OL-DOL equivalence problem
• Simple reductions between \(D0L\) language and sequence equivalence problems
• The decidability of the DOL-DTOL equivalence problem
• The decidability of the FOL-DOL equivalence problem
• The decidability of the equivalence problem for DOL-systems
• The equivalence problem for DF0L languages and power series.
• The equivalence problem for deterministic TOL-systems is undecidable

Cited in

(6)

• Lindenmayer systems
• Towards a proof of the decidability of the momentary stagnation of the growth function of D0L systems
• On D0L and HDT0L sets in monoids
• scientific article; zbMATH DE number 3864525 (Why is no real title available?)
• scientific article; zbMATH DE number 2016846 (Why is no real title available?)
• The equivalence problem for languages defined by transductions on D0L languages

This page was built for publication: The language equivalence problem for HD0L systems having D0L growths

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