On the equivalence of some transductions involving letter to letter morphisms on regular languages
type: Item
instance of: scholarly article
title: On the equivalence of some transductions involving letter to letter morphisms on regular languages
zbMATH Open document ID: 0564.68056
DOI: 10.1007/BF00288471
author: Yael Maon
published in: Acta Informatica
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 03D40
zbMATH DE Number: 3900179
zbMATH Keywords: decidability
zbMATH Keywords: Equivalence problems
zbMATH Keywords: regular languages
zbMATH Keywords: finite substitutions
MaRDI profile type: Publication
cites work: Test sets for context free languages and algebraic systems of equations over a free monoid
cites work: Q3859267
cites work: Single-valued a-transducers
cites work: Some decidability results about regular and pushdown translations
cites work: Systems of equations over a free monoid and Ehrenfeucht's conjecture
cites work: On the decidability of homomorphism equivalence for languages
cites work: The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
cites work: Q4198075
cites work: On some decision questions concerning pushdown machines
cites work: The Unsolvability of the Equivalence Problem for $\varepsilon $-Free NGSM’s with Unary Input (Output) Alphabet and Applications
cites work: Q3219110
cites work: A simple undecidable problem: Existential agreement of inverses of two morphisms on a regular language
cites work: Inverse morphic equivalence on languages
cites work: On the equivalence problem of compositions of morphisms and inverse morphisms on context-free languages
cites work: Balance of many-valued transductions and equivalence problems
cites work: Q4746787
full work available at URL: https://doi.org/10.1007/bf00288471
OpenAlex ID: W2033226842
description: scientific article; zbMATH DE number 3900179