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

DOI10.1142/S0129054103001960zbMATH Open1101.68660OpenAlexW1992229876MaRDI QIDQ5696933FDOQ5696933

Authors: Juhani Karhumäki, L. P. Lisovik 

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

Recommendations

• scientific article; zbMATH DE number 2086673
• Undecidability of the equivalence of finite substitutions on regular language
• The Simplest Language Where Equivalence of Finite Substitutions Is Undecidable
• Publication:4941151
• On the equivalence of some transductions involving letter to letter morphisms on regular languages

zbMATH Keywords

finite automataundecidabilityfinite languagesequivalence problems

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• The equivalence of finite valued transducers (on HDT0L languages) is decidable
• Remarks on blind and partially blind one-way multicounter machines
• The undecidability of some equivalence problems concerning ngsm's and finite substitutions
• 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
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
• Sur les rélations rationnelles entre monoides libres
• A proof of Ehrenfeucht's conjecture
• The equivalence problem for deterministic two-tape automata
• Equations over finite sets of words and equivalence problems in automata theory
• Systems of equations over a free monoid and Ehrenfeucht's conjecture
• On some transducer equivalence problems for families of languages
• Undecidability of the equivalence of finite substitutions on regular language

Cited In (16)

• Finiteness and recognizability problems for substitution maps on two symbols
• The equivalence problem for finite substitutions in a regular language
• A simple undecidable problem: the inclusion problem for finite substitutions on \(ab^* c\)
• Finite transducers and rational transductions
• Decision problems for language equations
• Unique decipherability in the additive monoid of sets of numbers
• The Simplest Language Where Equivalence of Finite Substitutions Is Undecidable
• Unique decipherability in the monoid of languages: an application of rational relations
• The equivalence problem for languages defined by transductions on D0L languages
• Language equations
• Unique Decipherability in the Monoid of Languages: An Application of Rational Relations
• On the equivalence of some transductions involving letter to letter morphisms on regular languages
• Title not available (Why is that?)
• A Burnside approach to the finite substitution problem
• Title not available (Why is that?)
• Title not available (Why is that?)

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

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