Sequentially indexed grammars
| Abstract | This paper defines the grammar class of sequentially indexed grammars. Sequentially indexed grammars are the result of a change in the index stack handling mechanism of indexed grammars [Aho68, Aho69]. Sequentially indexed grammars are different from linear indexed grammars [Gaz88]. Like indexed languages, sequentially indexed languages are a fully abstract language class. Unlike indexed languages, sequentially indexed languages allow polynomial parsing algorithms. We give a polynomial algorithm for parsing with sequentially indexed gramamrs that is an extension of the Earley algorithm for parsing with context free grammars. | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | No categories specified (fix it) | |||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,701 |
| External links |
  Try with proxy. Try with proxy. |
| Through your library | Only published papers are available at libraries |
Similar books and articlesDenis Béchet, Annie Foret & Isabelle Tellier (2007). Learnability of Pregroup Grammars. Studia Logica 87 (2-3):225 - 252.
Adrian Miroiu (1999). Actuality and World-Indexed Sentences. Studia Logica 63 (3):311-330.
Adam Obtułowicz (1989). Categorical and Algebraic Aspects of Martin-Löf Type Theory. Studia Logica 48 (3):299 - 317.
Anne Preller (2007). Linear Processing with Pregroups. Studia Logica 87 (2-3):171 - 197.
Daniel Feinstein & Shuly Wintner (2008). Highly Constrained Unification Grammars. Journal of Logic, Language and Information 17 (3).
Stephan Kepser & Jim Rogers (2011). The Equivalence of Tree Adjoining Grammars and Monadic Linear Context-Free Tree Grammars. Journal of Logic, Language and Information 20 (3):361-384.
Thomas Ehrhard (2004). A Completeness Theorem for Symmetric Product Phase Spaces. Journal of Symbolic Logic 69 (2):340 - 370.
Analytics
Monthly downloads |
Added to index2009-01-28Total downloads2 ( #232,575 of 549,124 )Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
