A new bound for the D0L sequence equivalence problem

DOI10.1007/S00236-006-0028-6zbMATH Open1106.68060OpenAlexW1980241523MaRDI QIDQ855272FDOQ855272

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

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Elementary homomorphisms and a solution of the DOL sequence equivalence problem
• A short solution for the HDT0L sequence equivalence problem
• Explicit test sets for iterated morphisms in free monoids and metabelian groups
• Title not available (Why is that?)
• On the equivalence problem for binary DOL systems
• The decidability of the equivalence problem for DOL-systems
• On a bound for the DOL sequence equivalence problem
• The equivalence problem of polynomially bounded D0L systems -- a bound depending only on the size of the alphabet
• An \(n^2\)-bound for the ultimate equivalence problem of certain D0L systems over an \(n\)-letter alphabet

Cited In (16)

• On the Images of ℕ-Rational Sequences Counting Multiplicities
• Title not available (Why is that?)
• A new bound for the D0L language equivalence problem
• Bounds for the D0L language equivalence problem
• A polynomial bound for certain cases of the D0L sequence equivalence problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• New Extensions and Applications of Welch-Bound-Equality Sequence Sets
• The equality problem for infinite words generated by primitive morphisms
• Title not available (Why is that?)
• An \(n^2\)-bound for the ultimate equivalence problem of certain D0L systems over an \(n\)-letter alphabet
• D0L sequence equivalence is inPfor fixed alphabets
• Title not available (Why is that?)
• Easy cases of the D0L sequence equivalence problem
• Title not available (Why is that?)
• The sequence equivalence problem for marked DT0L systems

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)