Powerful and NP-complete: hypergraph Lambek grammars

DOI10.1007/978-3-030-78946-6_6zbMATH Open1492.68073OpenAlexW3173814003MaRDI QIDQ2117261FDOQ2117261

Authors Tikhon Pshenitsyn

Publication date 21 March 2022

Full work available at URL https://doi.org/10.1007/978-3-030-78946-6_6

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• Hypergraph basic categorial grammars
• The complexity of graph languages generated by hyperedge replacement
• Hyperedge replacement: grammars and languages
• scientific article; zbMATH DE number 4060748
• HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting

Cites work

• scientific article; zbMATH DE number 3148870 (Why is no real title available?)
• scientific article; zbMATH DE number 7456053 (Why is no real title available?)
• Graph transformation. 13th international conference, ICGT 2020, held as part of STAF 2020, Bergen, Norway, June 25--26, 2020. Proceedings
• Lambek calculus is NP-complete
• Multimodal linguistic inference
• Product-free Lambek calculus and context-free grammars
• Second-order abstract categorial grammars as hyperedge replacement grammars
• The Mathematics of Sentence Structure

Cited in

(12)

• The string generating power of context-free hypergraph grammars
• Recognising \(k\)-connected hypergraphs in cubic time
• String Generating Hypergraph Grammars with Word Order Restrictions
• Grammars based on a logic of hypergraph languages
• Hypergraph Lambek grammars
• Hypergraph basic categorial grammars
• From double pushout grammars to hypergraph Lambek grammars with and without exponential modality
• Graph Transformations
• Context-free hypergraph grammars have the same term-generating power as attribute grammars
• scientific article; zbMATH DE number 177442 (Why is no real title available?)
• Lambek Grammars with One Division Are Decidable in Polynomial Time
• scientific article; zbMATH DE number 165817 (Why is no real title available?)

This page was built for publication: Powerful and NP-complete: hypergraph Lambek grammars

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117261)