Petri nets, Horn programs, linear logic and vector games

DOI10.1016/0168-0072(94)00060-GzbMath0829.03007MaRDI QIDQ1899147

Max I. Kanovich

Publication date: 4 October 1995

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

complexitysemanticsconcurrencycomputation theoryfragments of linear logicnondeterministic Minsky machines

Mathematics Subject Classification ID

Applications of game theory (91A80) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Logic in computer science (03B70) Automata and formal grammars in connection with logical questions (03D05) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Subsystems of classical logic (including intuitionistic logic) (03B20)

Related Items

State of the Art in Logics for Verification of Resource-Bounded Multi-Agent Systems, Debits and Credits in Petri Nets and Linear Logic, Nonelementary Complexities for Branching VASS, MELL, and Extensions, A Survey of the Proof-Theoretic Foundations of Logic Programming, Commutative Lambek grammars, Unnamed Item, Collaborative planning with confidentiality, Unnamed Item, Phase semantics and Petri net interpretation for resource-sensitive strong negation, Formalizing Operational Semantic Specifications in Logic, A proof theory for model checking

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear logic
• On the unity of logic
• Computational interpretations of linear logic
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Petri nets are monoids
• Language in action
• A game semantics for linear logic
• Decision problems for propositional linear logic
• Bounded linear logic: A modular approach to polynomial-time computability
• Linear logic as a logic of computations
• The complexity of Horn fragments of linear logic
• The complexity of the word problems for commutative semigroups and polynomial ideals
• Parallel program schemata
• On the computational power of pushdown automata
• An Algorithm for the General Petri Net Reachability Problem
• A new constructive logic: classic logic
• From petri nets to linear logic