Context-free commutative grammars with integer counters and resets

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

Christoph Haase, Simon Halfon, Dmitry Chistikov

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 sumvector addition systems with statesPresburger arithmeticreset netscommunication-free Petri netscontext-free commutative grammars

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

Expressive Power of Broadcast Consensus Protocols ⋮ Directed reachability for infinite-state systems ⋮ Reachability problems in low-dimensional nondeterministic polynomial maps over integers ⋮ Unnamed Item

Uses Software

• Easychair

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Mathematical foundations of computer science 2013. 38th international symposium, MFCS 2013, Klosterneuburg, Austria, August 26--30, 2013. Proceedings
• Dominoes and the complexity of subclasses of logical theories
• On the reachability problem for 5-dimensional vector addition systems
• A structure to decide reachability in Petri nets
• The equality problem for vector addition systems is undecidable
• The covering and boundedness problems for vector addition systems
• Remarks on blind and partially blind one-way multicounter machines
• On reachability equivalence for BPP-nets
• Sequential grammars and automata with valences
• On the complexity of pattern matching for highly compressed two-dimensional texts.
• Approaching the coverability problem continuously
• Semigroups, Presburger formulas, and languages
• Complexity Analysis of Continuous Petri Nets
• Complexity Results for Problems of Communication-Free Petri Nets and Related Formalisms
• Semilinearity and Context-Freeness of Languages Accepted by Valence Automata
• Reachability in Register Machines with Polynomial Updates
• Completeness Results for Generalized Communication-free Petri Nets with Arbitrary Arc Multiplicities
• Reachability in Succinct and Parametric One-Counter Automata
• Commutative grammars: The complexity of uniform word problems
• Integer Vector Addition Systems with States
• Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets
• An Algorithm for the General Petri Net Reachability Problem
• The complexity of equivalence problems for commutative grammars
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• Reasoning about systems with many processes
• The taming of the semi-linear set
• Subclasses of presburger arithmetic and the weak EXP hierarchy
• Demystifying Reachability in Vector Addition Systems
• Unary Pushdown Automata and Straight-Line Programs
• Complexity of Problems of Commutative Grammars
• Automated Deduction – CADE-20
• Automata, Languages and Programming
• Nonprimitive recursive complexity and undecidability for Petri net equivalences

This page was built for publication: Context-free commutative grammars with integer counters and resets