D0L sequence equivalence is inPfor fixed alphabets

DOI10.1051/ita:2007037zbMath1144.68037MaRDI QIDQ3515467

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 sequences; polynomial encoding of words

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

Related Items

Marked D0L systems and the \(2n\)-conjecture, EQUALITY SETS OF MORPHIC WORD SEQUENCES

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new bound for the D0L sequence equivalence problem
• A proof of Ehrenfeucht's conjecture
• A simple proof of the Skolem-Mahler-Lech theorem
• On a bound for the DOL sequence equivalence problem
• Elementary homomorphisms and a solution of the DOL sequence equivalence problem
• The equivalence problem of polynomially bounded D0L systems -- a bound depending only on the size of the alphabet
• A short solution for the HDT0L sequence equivalence problem
• The zero multiplicity of linear recurrence sequences
• The presence of a zero in an integer linear recurrent sequence is NP-hard to decide
• Explicit test sets for iterated morphisms in free monoids and metabelian groups
• An \(n^2\)-bound for the ultimate equivalence problem of certain D0L systems over an \(n\)-letter alphabet
• On a theorem of Marshall Hall
• On the equivalence problem for binary DOL systems
• Deux propriétés décidables des suites récurrentes linéaires
• The decidability of the equivalence problem for DOL-systems
• A polynomial bound for certain cases of the D0L sequence equivalence problem