On the equivalence of some transductions involving letter to letter morphisms on regular languages (Q1058303): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Revision as of 03:03, 5 March 2024
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
