Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
435946 | Theoretical Computer Science | 2015 | 31 Pages |
Abstract
Categorial Dependency Grammars (CDGs) are classical categorial grammars extended by oriented polarized valencies. At the same time, CDGs represent a class of completely lexicalized dependency grammars. They express both projective and non-projective dependencies. CDGs generate non-context-free languages. At that, they are parsed in polynomial time under realistic conditions. CDGs possess a normal form that is analogous to Greibach normal form for cf-grammars. CDG-languages are closed under almost all AFL operations and are accepted by a special class of push-down automata with independent counters.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Michael Dekhtyar, Alexander Dikovsky, Boris Karlov,