On the Complexity of Equivalence and Minimisation for Q-weighted Automata

Journal article

We present KReach, a tool for deciding reachability in general Petri nets. The tool is a full implementation of Kosaraju’s original 1982 decision procedure for reachability in VASS. We believe this to be the first implementation of its kind. We include a comprehensive suite of libraries for development with Vector Addition Systems (with States) in the Haskell programming language. KReach serves as a practical tool, and acts as an effective teaching aid for the theory behind the algorithm. Preliminary tests suggest that there are some classes of Petri nets for which we can quickly show unreachability. In particular, using KReach for coverability problems, by reduction to reachability, is competitive even against state-of-the-art coverability checkers

Authors: Kiefer, S; Murawski, A; Ouaknine, J; Wachter, B; Worrell, J

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Logical Methods in Computer Science
• Journal: Logical Methods in Computer Science
• Volume: Volume 9, Issue 1
• Publication date: 2013-03-04
• DOI: 10.2168/lmcs-9(1:8)2013
• ISSN: 1860-5974
• Language: English
• Keywords: Theoretical computer science; Timed automaton; Combinatorics; Pushdown automaton; Computer science; Equivalence (formal languages); Finite-state machine; Mathematics; Automata theory; Automaton; Algorithm; Quantum finite automata; Discrete mathematics