Unidirectional Lambek Grammars in Polynomial Time
| Autor: | Yury Savateev |
|---|---|
| Rok vydání: | 2009 |
| Předmět: |
Tree-adjoining grammar
Discrete mathematics TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Computational Theory and Mathematics Noncommutative logic Stochastic context-free grammar Context-sensitive grammar Indexed grammar Context-free grammar L-attributed grammar Phrase structure grammar Theoretical Computer Science Mathematics |
| Zdroj: | Theory of Computing Systems. 46:662-672 |
| ISSN: | 1433-0490 1432-4350 |
| DOI: | 10.1007/s00224-009-9208-4 |
| Popis: | Lambek grammars provide a useful tool for studying formal and natural languages. The generative power of unidirectional Lambek grammars equals that of context-free grammars. However, no feasible algorithm was known for deciding membership in the corresponding formal languages. In this paper we present a polynomial algorithm for deciding whether a given word belongs to a language generated by a given unidirectional Lambek grammar. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink