A simple undecidable problem: Existential agreement of inverses of two morphisms on a regular language
type: Item
instance of: scholarly article
title: A simple undecidable problem: Existential agreement of inverses of two morphisms on a regular language
zbMATH Open document ID: 0615.68051
DOI: 10.1016/0022-0000(86)90032-2
published in: Journal of Computer and System Sciences
publication date: 1986-01-01T00:00:00Z
review text: We show that it is undecidable whether or not for a given finite language F and for morphisms h and g the relation \(h^{-1}(x)\cap g^{-1}(x)\neq \emptyset\) holds for all x in \(F^*\cap (dom(h^{-1})\cup dom(g=^{- 1}))\), i.e., whether or not \(h^{-1}\) and \(g^{-1}\) existentially agree on \(F^*\).
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3997180
zbMATH Keywords: finite language
zbMATH Keywords: morphisms
author: Juhani Karhumäki
author: Yael Maon
MaRDI profile type: Publication
full work available at URL: 0022-0000(86)90032-2
OpenAlex ID: W2010411091
cites work: Q3859267
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: Q3736916
cites work: Inverse morphic equivalence on languages
cites work: Q3674079
description: scientific article; zbMATH DE number 3997180