Pregroup grammars with letter promotions: complexity and context-freeness

DOI10.1016/J.JCSS.2011.12.010zbMath1250.68138OpenAlexW2014390237MaRDI QIDQ1757847

Katarzyna Moroz, Zhe Lin, Wojciech Buszkowski

Publication date: 6 November 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2011.12.010

zbMATH Keywords

computational complexitycontext-free grammarpregrouptype grammar

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Unnamed Item

Cites Work

• Unidirectional Lambek grammars in polynomial time
• Language in action. Categories, lambdas and dynamic logic
• Commutation-augmented pregroup grammars and mildly context-sensitive languages
• Lambek calculus is NP-complete
• A Savateev-Style Parsing Algorithm for Pregroup Grammars
• Fully Lexicalized Pregroup Grammars
• Sequent systems for compact bilinear logic
• Type grammars as pregroups
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Pregroup grammars with letter promotions: complexity and context-freeness