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
Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement [PDF]
Recently, it has been shown that every recursively enumerable language can be generated by a scattered context grammar with no more than three nonterminals. However, in that construction, the maximal number of nonterminals simultaneously rewritten during
Tomáš Masopust, Alexander Meduna
doaj +1 more source
Partial Learning of Recursively Enumerable Languages [PDF]
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Ziyuan Gao +2 more
openaire +4 more sources
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
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
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
Analyzing Robustness of Angluin's L$^*$ Algorithm in Presence of Noise [PDF]
Angluin's L$^*$ algorithm learns the minimal deterministic finite automaton (DFA) of a regular language using membership and equivalence queries. Its probabilistic approximatively correct (PAC) version substitutes an equivalence query by numerous random ...
Lina Ye +7 more
doaj +1 more source
Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages [PDF]
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 ...
Engelfriet, J., Rozenberg, G.
openaire +1 more source
Separating the Classes of Recursively Enumerable Languages Based on Machine Size [PDF]
In the late nineteen sixties it was observed that the r.e. languages form an infinite proper hierarchy [Formula: see text] based 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.
Jan van Leeuwen, Jirí Wiedermann
openaire +5 more sources

