D0L sequence equivalence is inPfor fixed alphabets

DOI10.1051/ITA:2007037zbMATH Open1144.68037OpenAlexW2084363451MaRDI QIDQ3515467FDOQ3515467

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On a theorem of Marshall Hall
• Elementary homomorphisms and a solution of the DOL sequence equivalence problem
• A short solution for the HDT0L sequence equivalence problem
• The zero multiplicity of linear recurrence sequences
• Explicit test sets for iterated morphisms in free monoids and metabelian groups
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• The presence of a zero in an integer linear recurrent sequence is NP-hard to decide
• A proof of Ehrenfeucht's conjecture
• 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
• A polynomial bound for certain cases of the D0L 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
• A new bound for the D0L sequence equivalence problem
• Title not available (Why is that?)

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)