Results 221 to 230 of about 52,651 (265)

Ambiguity in context free languages

Journal of the ACM, 1966
Four principal results about ambiguity in languages (i.e., context free languages) are proved. It is first shown that the problem of determining whether an arbitrary language is inherently ambiguous is recursively unsolvable. Then a decision procedure is presented for determining whether an arbitrary bounded grammar is ambiguous.
Seymour Ginsburg, Joseph S. Ullian
openaire   +2 more sources

Context-free languages

ACM SIGACT News, 1993
This paper introduces a new level into the Chomsky of formal languages. Specifically the content-free languages are a subset of the regular languages. Content-free languages have many interesting properties.
openaire   +2 more sources

On the Growth of Context-Free Languages

J. Autom. Lang. Comb., 2008
Journal of Automata, Languages and Combinatorics, Volume 13, Number 2, 2008, 95 ...
Flavio D'Alessandro, Stefano Varricchio
openaire   +1 more source

The Hardest Context-Free Language

SIAM Journal on Computing, 1973
There is a context-free language $L_0 $ such that every context-free language is an inverse homomorphic image of $L_0 $ or $L_0 - \{ e\} $. Hence the time complexity of recognition of $L_0 $ is the least upper bound for time complexity of recognition of context-free languages. A similar result holds for quasirealtime Turing machine languages.
openaire   +2 more sources

Kernels of Context-Free Languages

International Journal of Foundations of Computer Science
While the closure of a language family [Formula: see text] under certain language operations is the least family of languages which contains all members of [Formula: see text] and is closed under all of the operations, a kernel of [Formula: see text] is a maximal family of languages which is a sub-family of [Formula: see text] and is closed under all ...
Martin Kutrib, Luca Prigioniero
openaire   +2 more sources

Logics for context-free languages

1995
We define matchings, and show that they capture the essence of context-freeness. More precisely, we show that the class of context-free languages coincides with the class of those sets of strings which can be defined by sentences of the form ∃ bϕ, where ϕ is first order, b is a binary predicate symbol, and the range of the second order quantifier is ...
Clemens Lautemann, Thomas Schwentick, Denis Thérien   +2 more
openaire   +1 more source

On stochastic context-free languages

Information Sciences, 1971
In this paper, properties of normalized stochastic languages are discussed and alternative procedures for constructing the Chomsky and Greibach normal forms for normalized stochastic context-free grammar (nscfg) are presented. A normalized stochastic context-free language (nscf l) is defined in terms of a nscfg.
T. Huang, King-Sun Fu
openaire   +3 more sources

On intersections of context-free languages

Fundamenta Informaticae, 1980
Following the suggestion of Prof. S. Marcus we study the “Darboux properties” of the hierarchy of intersections of context-free languages, introduced by Liu and Weiner [5]. Some properties of the Parikh function defined on an intersection of context-free languages are infered.
openaire   +3 more sources

Circuits and Context-Free Languages

1999
Simpler proofs that DAuxPDA-TIME(polynomial) equals LOG(DCFL) and that SAC1 equals LOG(CFL) are given which avoid Sud-borough's multi-head automata [Sud78]. The first characterization of LOGDCFL in terms of polynomial proof-tree-size is obtained, using circuits built from the multiplex select gates of [FLR96].
Pierre McKenzie, Klaus Reinhardt, V. Vinay   +2 more
openaire   +1 more source

On the recognition of context-free languages

1985
In this paper we present two results concerning the time and space complexity of context-free recognition. The first result states that cfl's can be recognized on a cube-connected computer (CCC) or on a perfect-shuffle computer (PSC) in log2n time using n6 processors.
openaire   +2 more sources