Results 11 to 20 of about 550 (233)
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
openaire +3 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
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
Generating Languages by P Systems with Minimal Symport/Antiport [PDF]
Computer Science Journal of Moldova, 2006 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
On enhanced time-varying distributed H systems [PDF]
Computer Science Journal of Moldova, 2002 An enhanced time-varying distributed H system (ETVDH system) is a slightly different definition of the time-varying distributed H system (TVDH system) [9] and it was proposed by M. Margenstern and Yu.
Sergey Verlan
doaj +2 more sources
Separating the classes of recursively enumerable languages based on machine size [PDF]
, 2014 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ří
core +4 more sources
On Parsing Programming Languages with Turing-Complete Parser
Mathematics, 2023 A new parsing method based on the semi-Thue system is described. Similar to, but with more efficient implementation than Markov normal algorithms, it can be used for parsing any recursively enumerable language.
Boštjan Slivnik, Marjan Mernik
doaj +1 more source
Partial Learning of Recursively Enumerable Languages [PDF]
Theoretical Computer Science, 2013 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Ziyuan Gao +2 more
openaire +2 more sources