A new bound for the D0L sequence equivalence problem

DOI10.1007/S00236-006-0028-6MaRDI QIDQ855272zbMATHOpenAlexFDO

Authors Juha Honkala

Publication date 5 January 2007

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00236-006-0028-6

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• The sequence equivalence problem for primitive D0L systems
• 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
• Bounds for the D0L language equivalence problem
• A polynomial bound for certain cases of the D0L sequence equivalence problem

Cites work

• scientific article; zbMATH DE number 3990879 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3802813 (Why is no real title available?)
• A short solution for the HDT0L sequence equivalence problem
• An \(n^2\)-bound for the ultimate equivalence problem of certain D0L systems over an \(n\)-letter alphabet
• Elementary homomorphisms and a solution of the DOL sequence equivalence problem
• Explicit test sets for iterated morphisms in free monoids and metabelian groups
• On a bound for the DOL sequence equivalence problem
• On the equivalence problem for binary DOL systems
• 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

(22)

• Equality sets of binary D0L sequences
• On the Images of ℕ-Rational Sequences Counting Multiplicities
• The sequence equivalence problem for marked DT0L systems
• Equality sets of morphic word sequences
• Parallel complexity of iterated morphisms and the arithmetic of small numbers
• scientific article; zbMATH DE number 1819637 (Why is no real title available?)
• scientific article; zbMATH DE number 4045201 (Why is no real title available?)
• scientific article; zbMATH DE number 4090810 (Why is no real title available?)
• Marked D0L systems and the \(2n\)-conjecture
• A polynomial bound for certain cases of the D0L sequence equivalence problem
• New Extensions and Applications of Welch-Bound-Equality Sequence Sets
• A new bound for the D0L language equivalence problem
• scientific article; zbMATH DE number 176925 (Why is no real title available?)
• The equality problem for infinite words generated by primitive morphisms
• scientific article; zbMATH DE number 3940751 (Why is no real title available?)
• Easy cases of the D0L sequence equivalence problem
• D0L sequence equivalence is inPfor fixed alphabets
• The sequence equivalence problem for primitive D0L systems
• D0L sequences and their equality sets
• An \(n^2\)-bound for the ultimate equivalence problem of certain D0L systems over an \(n\)-letter alphabet
• scientific article; zbMATH DE number 1860695 (Why is no real title available?)
• Bounds for the D0L language equivalence problem

This page was built for publication: A new bound for the D0L sequence equivalence problem

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