Equality sets for recursively enumerable languages [PDF]
We consider shifted equality sets of the form EG(a, g1 ,g 2 )= {w | g1(w )= ag2(w)} ,w hereg1 and g2 are nonerasing morphisms and a is a letter. We are interested in the family consisting of the languages h(EG(J)), where h is a coding and EG(J )i s as hifted equality set. We prove several closure properties for this family.
Vesa Halava +3 more
openaire +4 more sources
Intersection-closed full AFL and the recursively enumerable languages
A study is made of conditions on a language L which ensure that the smallest intersection-closed full AFL containing L (written ℱ^∩(L)) does or does not contain all recursively enumerable languages. For example, it is shown that if L = {ani/j⩾0} and limi→∞ inf(ni+1/ni) > 1, then ℱ^∩(L) contains all recursively enumerable languages.
Seymour Ginsburg, Jonathan Goldstine
openaire +3 more sources
Generating Languages by P Systems with Minimal Symport/Antiport [PDF]
It is known that P systems with two membranes and minimal symport/antiport rules are “almost” computationally complete as generators of number or vector sets.
Artiom Alhazov, Yurii Rogozhin
doaj +2 more sources
Separating the classes of recursively enumerable languages based on machine size
In the late nineteen sixties it was observed that the recursively enumerable languages form an infinite proper hierarchy bassed on the size of the Turing machines that accept them. We examine the fundamental position of the finite languages and their complements in the hierarchy.
van Leeuwen, Jan, Wiedermann, Jiří
openaire +2 more sources
Dyck Reductions of Minimal Linear Languages Yield the Full Class of Recursively Enumerable Languages [PDF]
application/pdf In this paper, we give a direct proof of the result of Latteux and Turakainen that the full class of recursively enumerable languages can be obtained from minimal linear languages (which are generated by linear context-free grammars with only one nonterminal symbol) by Dyck reductions (which reduce pairs of parentheses to the empty word)
12093 +4 more
core +3 more sources
On the Size Complexity of Non-Returning Context-Free PC Grammar Systems [PDF]
Improving the previously known best bound, we show that any recursively enumerable language can be generated with a non-returning parallel communicating (PC) grammar system having six context-free components.
Erzsébet Csuhaj-Varjú, György Vaszil
doaj +1 more source
Transformation of Turing Machines into Context-Dependent Fusion Grammars [PDF]
Context-dependent fusion grammars were recently introduced as devices for the generation of hypergraph languages. In this paper, we show that this new type of hypergraph grammars, where the application of fusion rules is restricted by positive and ...
Aaron Lye
doaj +1 more source
Turing machines based on unsharp quantum logic [PDF]
In this paper, we consider Turing machines based on unsharp quantum logic. For a lattice-ordered quantum multiple-valued (MV) algebra E, we introduce E-valued non-deterministic Turing machines (ENTMs) and E-valued deterministic Turing machines (EDTMs ...
Yun Shang, Xian Lu, Ruqian Lu
doaj +1 more source
Representation Theorem Using DOS Languages ; CU-CS-161-79 [PDF]
It is demonstrated that every context-free language is a homomorphic image of the intersection of two DOS languages and that every recursively enumerable language is the homomorphic image of the intersection of three DOS languages. It is also proved that
Rozenberg, Grzegorz +1 more
core +5 more sources
CLASSIFICATIONS OF GENERALIZED INDEX SETS OF BOOLEAN COMBINATIONS OF RECURSIVELY ENUMERABLE SETS.
CLASSIFICATIONS OF GENERALIZED INDEX SETS OF BOOLEAN COMBINATIONS OF RECURSIVELY ENUMERABLE ...
NANCY JO. JOHNSON (7968440)
core +4 more sources

