Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets

DOI10.1007/978-3-642-15155-2_54zbMath1287.68059OpenAlexW1508360721MaRDI QIDQ3586117

Philippe Schnoebelen

Publication date: 3 September 2010

Published in: Mathematical Foundations of Computer Science 2010 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-15155-2_54

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (27)

Zeno, Hercules, and the Hydra ⋮ Ideal Abstractions for Well-Structured Transition Systems ⋮ Forward analysis and model checking for trace bounded WSTS ⋮ Unnamed Item ⋮ Context-free commutative grammars with integer counters and resets ⋮ Nonelementary Complexities for Branching VASS, MELL, and Extensions ⋮ Undecidable Propositional Bimodal Logics and One-Variable First-Order Linear Temporal Logics with Counting ⋮ Coverability and Termination in Recursive Petri Nets ⋮ Unnamed Item ⋮ Relating timed and register automata ⋮ Aeolus: a component model for the cloud ⋮ Expressive Power of Broadcast Consensus Protocols ⋮ Computable fixpoints in well-structured symbolic model checking ⋮ Ordinal recursive complexity of unordered data nets ⋮ Hardness Results for Coverability Problem of Well-Structured Pushdown Systems ⋮ Decidability and complexity of Petri nets with unordered data ⋮ Multiset rewriting for the verification of depth-bounded processes with name binding ⋮ Unnamed Item ⋮ Petri nets with name creation for transient secure association ⋮ The ideal view on Rackoff's coverability technique ⋮ On the termination and structural termination problems for counter machines with incrementing errors ⋮ On Freeze LTL with Ordered Attributes ⋮ Coverability Trees for Petri Nets with Unordered Data ⋮ The Parametric Complexity of Lossy Counter Machines ⋮ Complexity Hierarchies beyond Elementary ⋮ Unnamed Item ⋮ Coverability, Termination, and Finiteness in Recursive Petri Nets

This page was built for publication: Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets