A simple undecidable problem: the inclusion problem for finite substitutions on ab^* c

DOI10.1016/S0890-5401(03)00120-2MaRDI QIDQ1887138zbMATH OpenOpenAlexFDO

Authors L. P. Lisovik, Juhani Karhumäki

Publication date 23 November 2004

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0890-5401(03)00120-2

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 1688379
• scientific article; zbMATH DE number 2086673
• The undecidability of some equivalence problems concerning ngsm's and finite substitutions
• The Equivalence Problem of Finite Substitutions on ab*c, with Applications
• Simple permutations: Decidability and unavoidable substructures
• Some undecidable embedding problems for finite semigroups
• Finiteness and recognizability problems for substitution maps on two symbols
• Publication:4508453
• Some undecidable problems about the trace-subshift associated to a Turing machine
• On the decidability of infix inclusion problem

Cites work

• An undecidable problem for countable markov chains
• Conway's problem for three-word sets.
• Equivalence problems for transducers with a bounded number of states
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3569855 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 2086673 (Why is no real title available?)
• scientific article; zbMATH DE number 1408337 (Why is no real title available?)
• scientific article; zbMATH DE number 3366846 (Why is no real title available?)
• On some transducer equivalence problems for families of languages
• On the equivalence of some transductions involving letter to letter morphisms on regular languages
• On the equivalence problem for binary DOL systems
• The commutation of finite sets: A challenging problem
• The equivalence problem for finite substitutions in a regular language
• The undecidability of some equivalence problems concerning ngsm's and finite substitutions
• Undecidability of the equivalence of finite substitutions on regular language

Cited in

(5)

• The undecidability of some equivalence problems concerning ngsm's and finite substitutions
• Some decision problems concerning semilinearity and commutation.
• Simple permutations: Decidability and unavoidable substructures
• The Simplest Language Where Equivalence of Finite Substitutions Is Undecidable
• Finiteness and recognizability problems for substitution maps on two symbols

This page was built for publication: A simple undecidable problem: the inclusion problem for finite substitutions on \(ab^* c\)

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