Results 1 to 10 of about 115 (104)
A homomorphic characterization of recursively enumerable languages
Theoretical Computer Science, 1985 We give a homomorphic characterization of the class of recursively enumerable languages: it is shown that any recursively enumerable language is the homomorphic image of the intersection of a Dyck language and a 'minimal linear' language.
Sadaki Hirose +2 more
exaly +2 more sources
Representing recursively enumerable languages by iterated deletion
Theoretical Computer Science, 2004 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Michael Domaratzki, Alexander Okhotin
exaly +3 more sources
Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages [PDF]
Journal of the ACM, 1980 Fixed point languages and equality languages of homomorphisms and dgsm mappings are consid- ered. Some basic properties of these classes of languages are proved, and it is shown how to use them to represent recursively enumerable sets. In particular, very simple languages are introduced which play the same role for the class of recursively enumerable ...
G Rozenberg
exaly +2 more sources
On representing recursively enumerable languages by internal contextual languages
Theoretical Computer Science, 1998 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Grzegorz Rozenberg +1 more
exaly +2 more sources
A representation of recursively enumerable languages by two homomorphisms and a quotient
Theoretical Computer Science, 1988 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 ...
Viliam Geffert
exaly +2 more sources
Information and Control, 1980 A method of encoding the computation histories of a wide class of machines is introduced and used to derive several representation theorems for the class of recursively enumerable languages. In particular it is demonstrated that any recursively enumerable language K ⊂ Σ* can be represented as K = ΦΣ(R ∩ D1 ⋮ D2), where D1 and D2 are fixed semi-Dyck ...
David Haussler, H. Paul Zeiger
exaly +2 more sources
Homomorphic characterizations of recursively enumerable languages with very small language classes
Theoretical Computer Science, 2001 In this paper, we attempt to characterize the class of recursively enumerable languages with much smaller language classes than that of linear languages. Language classes, \((i,j)\) LL and \((i,j)ML,\) of \((i,j)\) linear languages and \((i,j)\) minimal linear languages are defined by posing restrictions on the form of production rules and the number ...
Satoshi Okawa, Sadaki Hirose
exaly +2 more sources
Existential Definability over the Subword Ordering [PDF]
Logical Methods in Computer Science, 2023 We study first-order logic (FO) over the structure consisting of finite words over some alphabet $A$, together with the (non-contiguous) subword ordering.
Pascal Baumann +3 more
doaj +1 more source
Computational Power of P Systems with Small Size Insertion and Deletion Rules [PDF]
Electronic Proceedings in Theoretical Computer Science, 2009 Recent investigations show insertion-deletion systems of small size that are not complete and cannot generate all recursively enumerable languages.
Sergey Verlan +2 more
doaj +1 more source
Adding Matrix Control: Insertion-Deletion Systems with Substitutions III
Algorithms, 2021 Insertion-deletion systems have been introduced as a formalism to model operations that find their counterparts in ideas of bio-computing, more specifically, when using DNA or RNA strings and biological mechanisms that work on these strings.
Martin Vu, Henning Fernau
doaj +1 more source