A simple undecidable problem: Existential agreement of inverses of two morphisms on a regular language (Q1820585)
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: A simple undecidable problem: Existential agreement of inverses of two morphisms on a regular language |
scientific article; zbMATH DE number 3997180
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A simple undecidable problem: Existential agreement of inverses of two morphisms on a regular language |
scientific article; zbMATH DE number 3997180 |
Statements
A simple undecidable problem: Existential agreement of inverses of two morphisms on a regular language (English)
0 references
1986
0 references
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^*\).
0 references
finite language
0 references
morphisms
0 references
0 references
