Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
LC Graphs for the Lambek Calculus with Product
verfasst von : Timothy A. D. Fowler
Erschienen in: The Mathematics of Language
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
This paper introduces a novel graph representation of proof nets for the Lambek calculus that extends the LC graph representation of [13] to include the product connective. This graph representation more clearly specifies the difference between the Lambek calculus with and without product than other proof net representations, which is important to the search for polynomial time among Lambek calculus fragments. We use LC graphs to further the efforts to characterize the boundary between polynomial time and NP-complete sequent derivability by analyzing the NP-completeness proof of [14] and discussing a sequent derivability algorithm.