On the equivalence of some transductions involving letter to letter morphisms on regular languages (Q1058303)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the equivalence of some transductions involving letter to letter morphisms on regular languages |
scientific article |
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
