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

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

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Cites Work

• Lambek calculus is NP-complete
• The Mathematics of Sentence Structure
• Multimodal linguistic inference
• Product-free Lambek calculus and context-free grammars
• Graph transformation. 13th international conference, ICGT 2020, held as part of STAF 2020, Bergen, Norway, June 25--26, 2020. Proceedings
• Second-order abstract categorial grammars as hyperedge replacement grammars
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (10)

• String Generating Hypergraph Grammars with Word Order Restrictions
• The string generating power of context-free hypergraph grammars
• Title not available (Why is that?)
• Recognising \(k\)-connected hypergraphs in cubic time
• Title not available (Why is that?)
• Context-free hypergraph grammars have the same term-generating power as attribute grammars
• Grammars based on a logic of hypergraph languages
• Lambek Grammars with One Division Are Decidable in Polynomial Time
• Hypergraph Lambek grammars
• Graph Transformations

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)