Results 11 to 20 of about 501 (254)
Equality sets for recursively enumerable languages [PDF]
RAIRO - Theoretical Informatics and Applications, 2005 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
core +5 more sources
On representing recursively enumerable languages by internal contextual languages [PDF]
Theoretical Computer Science, 1998 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Andrzej Ehrenfeucht +2 more
openaire +2 more sources
Intersection-closed full AFL and the recursively enumerable languages [PDF]
Information and Control, 1971 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 +2 more sources
On the power of cooperation: a regular representation of recursively enumerable languages [PDF]
Theoretical Computer Science, 1991 A cooperating distributed grammar system (CDGS), as introduced by \textit{E. Csuhaj-Varju} and \textit{J. Dassow} [J. Inform. Process. Cybern. EIK 26, 49-63 (1990)] is a construct \(\gamma=(N,T,G_ 1,\dots\), \(G_ n,S)\), where \(N\), \(T\) are nonterminal and terminal vocabularies, \(S\in N\) and \(G_ i=(N_ i,T_ i,S_ i,P_ i)\) are grammars with \(N_ i ...
Erzsébet Csuhaj-Varjú, Jozef Kelemen
openaire +2 more sources
Characterizations of recursively enumerable languages by means of insertion grammars [PDF]
Theoretical Computer Science, 1998 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Carlos Martín-Vide +2 more
openaire +3 more sources
Very special languages and representations of recursively enumerable languages via computation histories [PDF]
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
openaire +3 more sources
A representation of recursively enumerable languages by two homomorphisms and a quotient [PDF]
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 ...
Geffert, Viliam
openaire +2 more sources
On characterization of recursively enumerable languages in terms of linear languages and VW-grammars [PDF]
Indagationes Mathematicae (Proceedings), 1978 AbstractIt is proved that for any alphabet Σ there exist a homomorphism h, a deterministic minimal linear language L1 and a linear language L2 such that every recursively enumerable language R over Σ is of the form L = h(L1 ∩ L2 ∪ RL) for some regular language RL depending on L. Some other homomorphic characterizations are also presented.
Turakainen, Paavo
openaire +3 more sources
Recursively enumerable languages and van Wijngaarden grammars [PDF]
Indagationes Mathematicae (Proceedings), 1977 AbstractWe show that each re language can be generated by a minimal deterministic linear contextfree based strict normal VW-grammar. We also prove that each re language can be generated by a strict normal VW-grammar with at most one metanotion denoting a non-regular contextfree language.
Van Leeuwen, Jan
openaire +3 more sources
Transformation of Turing Machines into Context-Dependent Fusion Grammars [PDF]
Electronic Proceedings in Theoretical Computer Science, 2019 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