Inverse morphic equivalence on languages
type: Item
instance of: scholarly article
title: Inverse morphic equivalence on languages
zbMATH Open document ID: 0571.68061
DOI: 10.1016/0020-0190(84)90055-3
author: Juhani Karhumäki
author: D. Wood
published in: Information Processing Letters
publication date: 1984-01-01T00:00:00Z
review text: The authors introduce the notion of inverse morphic equivalence of two morphisms g and h on a language L. Two variants are considered, the universal version, that is \(h^{-1}(x)=g^{-1}(x)\), for all x in L, and the existential version that is \(h^{-1}(x)\cap g^{-1}(x)\neq \emptyset\), for all x in L with \(h^{-1}(x)\cup g^{-1}(x)\neq \emptyset\). A finite subset F of a language L over \(\Delta\) is an inverse morphic equivalence test of L in the universal (respectively existential) sense if for all morphisms h and \(g:\Sigma^*\to \Delta^*\) the relation \(h^{-1}(x)=g^{-1}(x)\) for all x in \(F\cap (h(\Sigma^*)\cup g(\Sigma^*))\) implies the relation \(h^{-1}(x)=g^{-1}(x)\) for all x in \(L\cap (h(\Sigma^*)\cup g(\Sigma^*))\) [respectively the relation \(h^{-1}(x)\cap g^{-1}(x)\neq \emptyset\) for all x in \(F\cap (h(\Sigma^*)\cup g(\Sigma^*))\) implies the relation \(h^{-1}(x)\cap g^{-1}(x)\neq \emptyset\) for all x in \(L\cap (h(\Sigma^*)\cup g(\Sigma^*))]\). The paper discusses the existence of such test sets. Another section of the paper is dedicated to the decidability problem of whether or not two given inverse morphisms agree existentially or universally on a given language.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3911736
zbMATH Keywords: equality set
zbMATH Keywords: test set
zbMATH Keywords: decidability
zbMATH Keywords: inverse morphisms
reviewed by: R. Andonie
MaRDI profile type: Publication
full work available at URL: 0020-0190(84)90055-3
OpenAlex ID: W1985109353
cites work: Test sets for context free languages and algebraic systems of equations over a free monoid
cites work: Checking sets, test sets, rich languages and commutatively closed languages
cites work: Q3341932
cites work: Some decidability results about regular and pushdown translations
cites work: A homomorphic characterization of regular languages
cites work: Q3901701
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: On binary equality sets and a solution to the test set conjecture in the binary case
cites work: Rational sets in commutative monoids
cites work: An algorithm to generate the basis of solutions to homogeneous linear Diophantine equations
cites work: Q3736916
cites work: A note on morphic characterization of languages
cites work: Q3674079
cites work: Q4140407
cites work: A homomorphic characterization of principal semi AFLs without using intersection with regular sets
description: scientific article; zbMATH DE number 3911736