| |
Browse All Reviews > Theory Of Computation (F) > Mathematical Logic And Formal Languages (F.4) > Grammars And Other Rewriting Systems (F.4.2) > Grammar Types (F.4.2...)
|
|
 |
|
|
| |
|
|
| |
1-10 of 41
Reviews about "Grammar Types (F.4.2...)":
|
Date Reviewed |
| |
Characterization of context-free languages
Badano M., Vaggione D. Theoretical Computer Science 676 92-96, 2017. Type: Article
The authors prove that a generalized Greibach normal form (GNF) grammar still generates a context-free language. They expand the left side of GNF-type rules to be any nonempty product of variables (nonterminals), not just a single vari...
|
Sep 20 2018 |
| |
An extension of context-free grammars with one-sided context specifications
Barash M., Okhotin A. Information and Computation 237268-293, 2014. Type: Article
The gap between context-sensitive languages and context-free languages (types 1 and 2 in the Chomsky hierarchy) has been a rich area of research in formal language theory for the past five decades, giving rise to such mildly context-se...
|
Dec 16 2014 |
| |
Proofs and pedagogy; science and systems: the grammar tool box
Johnstone A., Scott E. Science of Computer Programming 69(1-3): 76-85, 2007. Type: Article
Generalized parsing of computer programs, unlike deterministic parsing, suffers from some theoretical as well as some practical problems: a lack of proofs of correctness, and an inability to compare competing algorithms....
|
Apr 7 2008 |
| |
Conjugacy and episturmian morphisms
Richomme G. Theoretical Computer Science 302(1-3): 1-34, 2003. Type: Article
The subword complexity of infinite words, W, is the research area covered in this paper. The subword complexity of W indicates, for any n, how many subwords (factors) of length <...
|
Oct 3 2003 |
| |
On parsing and condensing substrings of LR languages in linear time
Goeman H. Theoretical Computer Science 267(1-2): 61-82, 2001. Type: Article
The author offers a linear-time algorithm for recognizing substrings of LR(k) (and related) grammars. This has been attempted before, notably by Bates and Lavie [1]. Although Goeman is offering a critique of this earlier work, he need...
|
Sep 6 2002 |
| |
On parsing LL-languages
Blum N. Theoretical Computer Science 267(1-2): 49-59, 2001. Type: Article
LL(k) grammars are CFGs (context-free grammars) which can be parsed deterministically from left to right by looking forward at most k symbols at each step; traditionally implemented using a pushdown transducer....
|
Jul 10 2002 |
| |
Macro tree transducers, attribute grammars, and MSO definable tree translations
Engelfriet J., Maneth S. Information and Computation 154(1): 34-91, 1999. Type: Article
This paper continues a long series by the first author, alone and with others, beginning in 1975, all devoted to tree transformations--their properties and applications, especially in models for syntax-directed semantics as us...
|
Feb 1 2000 |
| |
Splicing on tree-like structures
Sakakibara Y., Ferretti C. Theoretical Computer Science 210(2): 227-243, 1999. Type: Article
Splicing systems are language-generating devices modeling theprocess by which molecular strings carrying genetic information are cutand recombined to form new strings. It is known that the regularlanguages can be generated from finite ...
|
Feb 1 2000 |
| |
The generating power of total deterministic tree transducer
Maneth S. Information and Computation 147(2): 111-144, 1998. Type: Article
This paper deals with the generating power of tree transducers.Maneth proves that attributed tree transducers and attribute grammarsgenerate the same class of term languages. In particular, heinvestigates top-down tree transducers. A h...
|
Aug 1 1999 |
| |
Griebach normal form transformation revisited
Blum N., Koch R. Information and Computation 150(1): 112-118, 1999. Type: Article
This paper develops a new method of converting an arbitrarycontext-free grammar G into one in Greibach normal form (GNF). (If a grammaris in GNF, the right-hand side of every production starts with aterminal.) Althou...
|
Aug 1 1999 |
| |
|
|
| |
|
|
