A polynomial bound for certain cases of the D0L sequence equivalence problem

DOI10.1007/S00224-001-0001-2MaRDI QIDQ5945725zbMATH OpenOpenAlexFDO

Authors Juha Honkala

Publication date 30 June 2002

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-001-0001-2

zbMATH Keywords

D0L sequence equivalence problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• A new bound for the D0L sequence equivalence problem
• scientific article; zbMATH DE number 3940751
• The equivalence problem of polynomially bounded D0L systems -- a bound depending only on the size of the alphabet
• A bound for theω-equivalence problem of polynomial D0L systems
• The sequence equivalence problem for primitive D0L systems
• D0L sequences and their equality sets
• An algorithm for deciding zero equivalence of nested polynomially recurrent sequences
• The Pólya algorithm in sequence spaces
• Easy cases of the D0L sequence equivalence problem
• D0L sequence equivalence is inPfor fixed alphabets

Cited in

(6)

• Explicit test sets for iterated morphisms in free monoids and metabelian groups
• D0L sequence equivalence is inPfor fixed alphabets
• A bound for theω-equivalence problem of polynomial D0L systems
• On infinite words generated by polynomial D0L systems
• Bounds for the D0L language equivalence problem
• A new bound for the D0L sequence equivalence problem

This page was built for publication: A polynomial bound for certain cases of the D0L sequence equivalence problem

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