A simple undecidable problem: the inclusion problem for finite substitutions on \(ab^* c\)
type: Item
instance of: scholarly article
title: A simple undecidable problem: the inclusion problem for finite substitutions on \(ab^* c\)
zbMATH Open document ID: 1082.68054
DOI: 10.1016/S0890-5401(03)00120-2
author: L. P. Lisovik
author: Juhani Karhumäki
published in: Information and Computation
publication date: 2004-11-23T00:00:00Z
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 2118404
MaRDI profile type: Publication
cites work: Q3859267
cites work: Q5639639
cites work: Q4714446
cites work: The commutation of finite sets: A challenging problem
cites work: Undecidability of the equivalence of finite substitutions on regular language
cites work: On the equivalence problem for binary DOL systems
cites work: Q4941151
cites work: Q4737210
cites work: Conway's problem for three-word sets.
cites work: An undecidable problem for countable markov chains
cites work: The equivalence problem for finite substitutions in a regular language
cites work: Equivalence problems for transducers with a bounded number of states
cites work: On the equivalence of some transductions involving letter to letter morphisms on regular languages
cites work: Q4140407
cites work: On some transducer equivalence problems for families of languages
cites work: The undecidability of some equivalence problems concerning ngsm's and finite substitutions
full work available at URL: s0890-5401(03)00120-2
OpenAlex ID: W2071584992
Recommended article: Q2762520
Recommended article: Q4737210
Recommended article: The undecidability of some equivalence problems concerning ngsm's and finite substitutions
Recommended article: The Equivalence Problem of Finite Substitutions on ab*c, with Applications
Recommended article: Simple permutations: Decidability and unavoidable substructures
Recommended article: Some undecidable embedding problems for finite semigroups
Recommended article: Finiteness and recognizability problems for substitution maps on two symbols
Recommended article: Q4508453
Recommended article: Q3455042
Recommended article: On the decidability of infix inclusion problem
description: scientific article; zbMATH DE number 2118404