Simple reductions between \(D0L\) language and sequence equivalence problems (Q1208490)
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: Simple reductions between \(D0L\) language and sequence equivalence problems |
scientific article; zbMATH DE number 166482
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Simple reductions between \(D0L\) language and sequence equivalence problems |
scientific article; zbMATH DE number 166482 |
Statements
Simple reductions between \(D0L\) language and sequence equivalence problems (English)
0 references
16 May 1993
0 references
It is known that both LE-D0L and SE-DOL problems are decidable and that any algorithm for solving one of them can be transformed into an algorithm for solving the other one. The author presents transformations essentially simpler than those existing in the references. The proof of total correctness of the algorithms is outlined. As the author remarks, the ideas might be useful also in other considerations dealing with morphisms on free monoids.
0 references
D0L language equivalence problem
0 references
D0L sequence equivalence problem
0 references
0.8933518
0 references
0.88735867
0 references
0 references
0.87377375
0 references
0.86805296
0 references
0.8674563
0 references
0.8652149
0 references
