Simple reductions between \(D0L\) language and sequence equivalence problems
type: Item
instance of: scholarly article
title: Simple reductions between \(D0L\) language and sequence equivalence problems
zbMATH Open document ID: 0788.68086
DOI: 10.1016/0166-218X(90)90061-G
published in: Discrete Applied Mathematics
publication date: 1993-05-16T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 166482
zbMATH Keywords: D0L language equivalence problem
zbMATH Keywords: D0L sequence equivalence problem
author: Arto Salomaa
reviewed by: Tudor Bălănescu
MaRDI profile type: Publication
cites work: On the decidability of some equivalence problems for DOL-systems
cites work: Q3999090
cites work: Q4140407
Recommended article: Bounds for the D0L language equivalence problem
Recommended article: A new bound for the D0L language equivalence problem
Recommended article: The equivalence problem for languages defined by transductions on D0L languages
Recommended article: Q3782819
Recommended article: The equivalence problem for DF0L languages and power series.
Recommended article: The sequence equivalence problem for primitive D0L systems
Recommended article: On the equivalence problem of context-free and DT0L languages
Recommended article: The ω sequence problem for DOL systems is decidable
Recommended article: Q3471701
Recommended article: Decidability of the equivalence problem for deterministic pushdown automata
description: scientific article; zbMATH DE number 166482