The Equivalence Problem of Finite Substitutions on ab*c, with Applications
From MaRDI portal
Publication:5696933
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
Cites work
- A note on finite-valued and finitely ambiguous transducers
- A proof of Ehrenfeucht's conjecture
- Decomposing Finite-Valued Transducers and Deciding Their Equivalence
- Equations over finite sets of words and equivalence problems in automata theory
- On some transducer equivalence problems for families of languages
- Remarks on blind and partially blind one-way multicounter machines
- Sur les rélations rationnelles entre monoides libres
- Systems of equations over a free monoid and Ehrenfeucht's conjecture
- The Unsolvability of the Equivalence Problem for $\varepsilon $-Free NGSM’s with Unary Input (Output) Alphabet and Applications
- The equivalence of finite valued transducers (on HDT0L languages) is decidable
- The equivalence problem for deterministic two-tape automata
- The undecidability of some equivalence problems concerning ngsm's and finite substitutions
- The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
- Undecidability of the equivalence of finite substitutions on regular language
Cited in
(16)- On the equivalence of some transductions involving letter to letter morphisms on regular languages
- A simple undecidable problem: the inclusion problem for finite substitutions on \(ab^* c\)
- Finite transducers and rational transductions
- Unique decipherability in the additive monoid of sets of numbers
- Unique Decipherability in the Monoid of Languages: An Application of Rational Relations
- Language equations
- scientific article; zbMATH DE number 2086673 (Why is no real title available?)
- scientific article; zbMATH DE number 1688379 (Why is no real title available?)
- The Simplest Language Where Equivalence of Finite Substitutions Is Undecidable
- scientific article; zbMATH DE number 1408337 (Why is no real title available?)
- Decision problems for language equations
- The equivalence problem for finite substitutions in a regular language
- A Burnside approach to the finite substitution problem
- Finiteness and recognizability problems for substitution maps on two symbols
- Unique decipherability in the monoid of languages: an application of rational relations
- The equivalence problem for languages defined by transductions on D0L languages
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)
