Results 231 to 240 of about 52,651 (265)
Some of the next articles are maybe not open access.
On context-free and Szilard languages
BIT, 1984The Szilard language of a context-free grammar is context-free if and only if the grammar is ''half-bounded'', i.e. if there is a natural number k such that each sentential form contains at most k occurrences of all but possibly one nonterminal. However, it is quite natural to expect that also non-context-free Szilard languages of context-free grammars
openaire +2 more sources
Caterpillars and context-free languages
1990We use the concept of a caterpillar tree to study the properties of context-free languages, in particular new results about the index of context-free languages and the recognition of context-free languages are obtained this way. The first group of results points to differences between ambiguous and unambiguous languages.
Michal Chytil, Burkhard Monien
openaire +1 more source
On bounded context-free languages
J. Inf. Process. Cybern., 1984Two new characterizations of bounded context-free languages are established and two known conjectures concerning context-free languages are shown to be true for the particular case of bounded context-free languages.
Michel Latteux, Gabriel Thierrin
openaire +2 more sources
2007
In this paper, I present the class of linear context free languages (LCFLs) with a class of non-deterministic one-way two-head (read only) automata, called non-deterministic linear automata (NLA). At the begining of the work of an NLA, the reading heads are installed under the opposite ends of the given input string.
openaire +2 more sources
In this paper, I present the class of linear context free languages (LCFLs) with a class of non-deterministic one-way two-head (read only) automata, called non-deterministic linear automata (NLA). At the begining of the work of an NLA, the reading heads are installed under the opposite ends of the given input string.
openaire +2 more sources
Fundamenta Informaticae, 1986
We define a superclass of the class of context-free languages, denoted ACFL (almost context-free languages) and construct an infinite sequence of non-context-free languages of decreasing complexity, belonging to ACFL. The languages in ACFL share many important properties of context-free languages.
openaire +2 more sources
We define a superclass of the class of context-free languages, denoted ACFL (almost context-free languages) and construct an infinite sequence of non-context-free languages of decreasing complexity, belonging to ACFL. The languages in ACFL share many important properties of context-free languages.
openaire +2 more sources
Kins of context-free languages
2005We study languages which can be described as limits of fast converging infinite sequences of context-free languages. Such a sequence \(L_0 \subseteq L_1 \subseteq L_2 \subseteq\) ... is fast converging if each string w of its limit language belongs to an Li which has a grammatical description very concise in comparison with the length of w .
openaire +2 more sources
On the Density of Regular and Context-Free Languages
Discrete Mathematics, Algorithms and Applications, 2010The density of a language is defined as the function dL(n) = |L ∩ Σn| and counts the number of words of a certain length accepted by L. The study of the density of regular and context-free languages has attracted some attention culminating in the fact that such languages are either sparse, when the density can be bounded by a polynomial, or dense ...
openaire +3 more sources
Noncounting Context-Free Languages
Journal of the ACM, 1978CRESPI REGHIZZI, STEFANO +2 more
openaire +5 more sources
On Universally Polynomial Context-Free Languages
International Journal of Foundations of Computer Science, 2001A language is universally polynomial if its intersection with every NP-complete language is in P. Such a language would provide an automatic method for generating easy instances of intractable problems. In this note, we give a complete characterization of universally polynomial languages that are context-free, answering an open question in [4].
openaire +2 more sources
On slender context-free languages
1995In this paper we study slender context-free languages, i.e., those containing at most a constant number of words of each length. Recently, Ilie proved that every such language can be described by a finite union of terms of the form uv i wx i y [I]. We provide a completely different proof of this, using constructive methods.
openaire +1 more source