Context-free commutative grammars with integer counters and resets

DOI10.1016/j.tcs.2016.06.017zbMath1393.68087arXiv1511.04893MaRDI QIDQ2636518

Christoph Haase, Dmitry Chistikov, Simon Halfon

Publication date: 5 June 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.04893

zbMATH Keywords

subset sum; vector addition systems with states; Presburger arithmetic; reset nets; communication-free Petri nets; context-free commutative grammars

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

68Q42: Grammars and rewriting systems

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Uses Software

• Easychair