Context-free commutative grammars with integer counters and resets
作者： Dmitry Chistikov , Christoph Haase , Simon Halfon
DOI: 10.1016/J.TCS.2016.06.017
关键词: Computer science 、 Petri net 、 Subset sum problem 、 Integer 、 Discrete mathematics 、 Context (language use) 、 Presburger arithmetic 、 Computational complexity theory 、 Commutative property 、 Reachability
摘要: We study the computational complexity of reachability, coverability and inclusion for extensions context-free commutative grammars with integer counters reset operations on them. Those can alternatively be viewed as an extension communication-free Petri nets. Our main results are that reachability inter-reducible both NP-complete. In particular, this class enjoys semi-linear sets. also show problem is, in general, coNEXP-complete already Π2P-complete only one non-terminal symbol. Showing lower bound latter result requires us to develop a novel variant classic subset sum problem.
arxiv.org
warwick.ac.uk
sci-hub.se 参考文章(45)
Alain Finkel, Stefan Göller, Christoph Haase, Reachability in Register Machines with Polynomial Updates Mathematical Foundations of Computer Science 2013. pp. 409- 420 ,(2013) , 10.1007/978-3-642-40313-2_37
Matthew Hague, Anthony Widjaja Lin, Model checking recursive programs with numeric data types computer aided verification. pp. 743- 759 ,(2011) , 10.1007/978-3-642-22110-1_60
Simon Halfon, Christoph Haase, Integer Vector Addition Systems with States international workshop on reachability problems. pp. 112- 124 ,(2014) , 10.1007/978-3-319-11439-2_9
Hendrik Jan Hoogeboom, Context-Free Valence Grammars - Revisited developments in language theory. pp. 293- 303 ,(2001) , 10.1007/3-540-46011-X_25
Helmut Seidl, Thomas Schwentick, Anca Muscholl, Peter Habermehl, Counting in Trees for Free Automata, Languages and Programming. pp. 1136- 1149 ,(2004) , 10.1007/978-3-540-27836-8_94
Philippe Schnoebelen, Revisiting Ackermann-hardness for lossy counter machines and reset Petri nets mathematical foundations of computer science. ,vol. 6281, pp. 616- 628 ,(2010) , 10.1007/978-3-642-15155-2_54
C. Dufourd, A. Finkel, Ph. Schnoebelen, Reset Nets Between Decidability and Undecidability international colloquium on automata languages and programming. pp. 103- 115 ,(1998) , 10.1007/BFB0055044
Ernst W. Mayr, Jeremias Weihmann, Complexity Results for Problems of Communication-Free Petri Nets and Related Formalisms Fundamenta Informaticae. ,vol. 137, pp. 61- 86 ,(2015) , 10.3233/FI-2015-1170
Yen Hsu-Chun, On reachability equivalence for BPP-nets Theoretical Computer Science. ,vol. 179, pp. 301- 317 ,(1997) , 10.1016/S0304-3975(96)00147-8
Christoph Haase, Stephan Kreutzer, Joël Ouaknine, James Worrell, Reachability in Succinct and Parametric One-Counter Automata international conference on concurrency theory. ,vol. 5710, pp. 369- 383 ,(2009) , 10.1007/978-3-642-04081-8_25