On the equivalence of some transductions involving letter to letter morphisms on regular languages (Q1058303)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On the equivalence of some transductions involving letter to letter morphisms on regular languages |
scientific article; zbMATH DE number 3900179
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the equivalence of some transductions involving letter to letter morphisms on regular languages |
scientific article; zbMATH DE number 3900179 |
Statements
On the equivalence of some transductions involving letter to letter morphisms on regular languages (English)
0 references
1986
0 references
Equivalence problems of some transductions involving letter to letter morphisms on regular languages are discussed. In particular, we deal with finite substitutions and inverses of finite substitutions. Our main results are the following: (i) The equivalence problem of inverses of finite substitutions on regular languages is undecidable, (ii) The existential equivalence problem of finite substitutions on regular languages is undecidable, and (iii) The length-equivalence problem of finite substitutions on regular languages is decidable.
0 references
decidability
0 references
Equivalence problems
0 references
regular languages
0 references
finite substitutions
0 references
0 references
0 references
0 references
0 references
0 references
