The Equivalence Problem of Finite Substitutions on ab*c, with Applications

DOI10.1142/S0129054103001960zbMath1101.68660OpenAlexW1992229876MaRDI QIDQ5696933

L. P. Lisovik, Juhani Karhumäki

Publication date: 19 October 2005

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054103001960

zbMATH Keywords

undecidabilityfinite automatafinite languagesequivalence problems

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (7)

Unique decipherability in the monoid of languages: an application of rational relations ⋮ Decision problems for language equations ⋮ Unique decipherability in the additive monoid of sets of numbers ⋮ The equivalence problem for languages defined by transductions on D0L languages ⋮ Unique Decipherability in the Monoid of Languages: An Application of Rational Relations ⋮ Finite transducers and rational transductions ⋮ Language equations

Cites Work

• Equations over finite sets of words and equivalence problems in automata theory
• The equivalence problem for deterministic two-tape automata
• Systems of equations over a free monoid and Ehrenfeucht's conjecture
• A proof of Ehrenfeucht's conjecture
• The equivalence of finite valued transducers (on HDT0L languages) is decidable
• Sur les rélations rationnelles entre monoides libres
• Remarks on blind and partially blind one-way multicounter machines
• The undecidability of some equivalence problems concerning ngsm's and finite substitutions
• On some transducer equivalence problems for families of languages
• A note on finite-valued and finitely ambiguous transducers
• Decomposing Finite-Valued Transducers and Deciding Their Equivalence
• The Unsolvability of the Equivalence Problem for $\varepsilon $-Free NGSM’s with Unary Input (Output) Alphabet and Applications
• Undecidability of the equivalence of finite substitutions on regular language
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines

This page was built for publication: The Equivalence Problem of Finite Substitutions on ab*c, with Applications