D0L sequence equivalence is inPfor fixed alphabets

DOI10.1051/ITA:2007037MaRDI QIDQ3515467zbMATH OpenOpenAlexFDO

Authors Keijo Ruohonen

Publication date 29 July 2008

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/92876

zbMATH Keywords

\(\mathbb Z\)-rational sequencespolynomial encoding of words

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A new bound for the D0L sequence equivalence problem
• D0L sequences and their equality sets
• The sequence equivalence problem for primitive D0L systems
• A polynomial bound for certain cases of the D0L 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
• scientific article; zbMATH DE number 3940751
• Easy cases of the D0L sequence equivalence problem
• Equality sets of binary D0L sequences
• The ω sequence problem for DOL systems is decidable

Cites work

• 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 41838 (Why is no real title available?)
• scientific article; zbMATH DE number 3588051 (Why is no real title available?)
• scientific article; zbMATH DE number 1339966 (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?)
• scientific article; zbMATH DE number 3346453 (Why is no real title available?)
• A new bound for the D0L sequence equivalence problem
• A polynomial bound for certain cases of the D0L sequence equivalence problem
• A proof of Ehrenfeucht's conjecture
• A short solution for the HDT0L sequence equivalence problem
• A simple proof of the Skolem-Mahler-Lech theorem
• An \(n^2\)-bound for the ultimate equivalence problem of certain D0L systems over an \(n\)-letter alphabet
• Deux propriétés décidables des suites récurrentes linéaires
• 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 a theorem of Marshall Hall
• 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
• The presence of a zero in an integer linear recurrent sequence is NP-hard to decide
• The zero multiplicity of linear recurrence sequences

Cited in

(4)

• Marked D0L systems and the 2n-conjecture
• Equality sets of binary D0L sequences
• A polynomial bound for certain cases of the D0L sequence equivalence problem
• Equality sets of morphic word sequences

This page was built for publication: D0L sequence equivalence is inPfor fixed alphabets

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