Results 221 to 230 of about 501 (254)
Some of the next articles are maybe not open access.
A note on the recursive enumerability of some classes of recursively enumerable languages
Information Sciences, 1978Abstract An elementary proof is presented for the fact that the class of infinite recursive languages is not recursively enumerable. Its relevance for contemporary linguistics and computer science is explained.
Peter van Emde Boas, Paul M. B. Vitányi
openaire +2 more sources
Flow languages equal recursively enumerable languages
Acta Informatica, 1981Recently, A.C. Shaw introduced a new class of expressions called flow expressions, and conjectured that the formal descriptive power of flow expressions lies somewhat below context-sensitive grammers. In this paper, we give a negative answer for his conjecture, that is, we show that all recursively enumerable languages may be denoted by flow ...
Toshiro Araki, Nobuki Tokura
openaire +2 more sources
Closure properties for fuzzy recursively enumerable languages and fuzzy recursive languages
Journal of Intelligent & Fuzzy Systems, 2016There are several variations of fuzzy Turing machines in the literature, many of them require a t-norm in order to establish their accepted language. This paper generalize the concept of non-deterministic fuzzy Turing machine - NTFM, replacing the t-norm operator for several aggregation functions.
Antonio Diego Silva Farias +3 more
openaire +1 more source
Global Syntax and Semantics for Recursively Enumerable Languages
Fundamenta Informaticae, 1981According to (Benson, 1970), a syntax is a category of strings and derivations (modulo similarity) between them. In this paper the semantic domain is an elementary topes. Thus, an interpretation of a syntax is a cofunctor taking strigs to products and derivations to morphisms.
Cristian Calude, Gheorghe Paun
openaire +2 more sources
On Conservative Learning of Recursively Enumerable Languages
2013Conservative partial learning is a variant of partial learning whereby the learner, on a text for a target language L, outputs one index e with L = W e infinitely often and every further hypothesis d is output only finitely often and satisfies \(L \not\subseteq W_d\).
Ziyuan Gao +2 more
openaire +1 more source
Grammar systems as language analyzers and recursively enumerable languages
1999We consider parallel communicating grammar systems which consist of several grammars and perform derivation steps, where each of the grammars works in a parallel and synchronized manner on its own sentential form, and communication steps, where a transfer of sentential forms is done.
Henning Bordihn +2 more
openaire +1 more source
J. Autom. Lang. Comb., 1999
We prove that every recursively enumerable language can be generated by a programmed grammar with context-free core rules using unconditional transfer with left-most derivation of type 3 or type 2. Interestingly, we have to give a non-constructive proof of the first mentioned universality result based on Higman's lemma, since finding a transformation ...
Henning Fernau, Frank Stephan 0001
openaire +2 more sources
We prove that every recursively enumerable language can be generated by a programmed grammar with context-free core rules using unconditional transfer with left-most derivation of type 3 or type 2. Interestingly, we have to give a non-constructive proof of the first mentioned universality result based on Higman's lemma, since finding a transformation ...
Henning Fernau, Frank Stephan 0001
openaire +2 more sources
Polynomial Generators of Recursively Enumerable Languages
2005For each language L, let $\hat{\mathcal F}_\cap(L)$ be the smallest intersection-closed full AFL generated by the language L. Furthermore, for each natural number k≥ 2 let $P_k=\{a^{n^k}|n\in\mathbb N\}$. By applying certain classical and recent results on Diophantine equations we show that $\mathcal L_{RE}=\hat{\mathcal F}_\cap(P_k)$, i.e., the family
openaire +1 more source
A characterization of recursively enumerable languages
Bull. EATCS, 1991It is shown that each recursively enumerable language \(L\) can be written in the form \(L=\text{red}(L_ 0)\cap V^*\), where red is the reduction operation considered in \textit{H. A. Maurer}, \textit{G. Rozenberg} and \textit{E. Welzl} [Inf. Control 54, 155-185 (1982; Zbl 0523.68065)], \(L_ 0\) is a linear language, and \(V\) is the alphabet of \(L\).
openaire +1 more source
On characterizing recursively enumerable languages by insertion grammars
Fundam. Informaticae, 2005Summary: Previously, it was proved that insertion grammars with weight at least 7 can characterize recursively enumerable languages (modulo a weak coding and an inverse morphism), and the question was formulated whether or not this result can be improved. In this paper, we come up with a positive answer to this question, by decreasing the weight of the
Madhu Mutyam +2 more
openaire +2 more sources