Explicit test sets for iterated morphisms in free monoids and metabelian groups

DOI10.1016/j.tcs.2004.09.017zbMath1078.68094OpenAlexW2029946359MaRDI QIDQ1763708

Keijo Ruohonen

Publication date: 22 February 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.09.017

zbMATH Keywords

Iterated morphismHD0L equivalenceTest set

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items

The equivalence of finite valued transducers (on HDT0L languages) is decidable, A new bound for the D0L sequence equivalence problem, D0L sequence equivalence is inPfor fixed alphabets, 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A proof of Ehrenfeucht's conjecture
• A simple proof of the Skolem-Mahler-Lech theorem
• 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
• Decimations of linear recurring sequences
• The zero multiplicity of linear recurrence sequences
• The presence of a zero in an integer linear recurrent sequence is NP-hard to decide
• Binary equality sets are generated by two words
• On the Images of ℕ-Rational Sequences Counting Multiplicities
• DECIDABILITY OF THE UNIVERSAL AND POSITIVE THEORIES OF A FREE GROUP
• On the equivalence problem for binary DOL systems
• Deux propriétés décidables des suites récurrentes linéaires
• The Algorithmic Theory of Finitely Generated Metabelian Groups
• Finiteness Conditions for Soluble Groups
• A polynomial bound for certain cases of the D0L sequence equivalence problem