A representation of recursively enumerable languages by two homomorphisms and a quotient (Q1115633): Difference between revisions

For two strings x and y, \(x\setminus y\) is the string z when \(y=xz\); otherwise \(x\setminus y\) is undefined. The author proves the following representation theorem: For each recursively enumerable set L (over alphabet \(\Sigma)\) there exist two homomorphisms \(h_ 1\), \(h_ 2:\) \(\Sigma^*_ 1\to \Sigma^*_ 2\) \((\Sigma \subseteq \Sigma_ 2)\) such that for every \(w\in \Sigma^*\), \(w\in L\) if and only if \(w=h_ 1(x)\setminus h_ 2(x)\) for some \(x\in \Sigma^*_ 1.\) The author discusses some complexity issues related to this representation and also some variants of the representation result.