The Ordinal-Recursive Complexity of Timed-arc Petri Nets, Data Nets, and Other Enriched Nets

DOI10.1109/LICS.2012.46zbMath1362.68214MaRDI QIDQ2986811

Sylvain Schmitz, Serge Haddad, Philippe Schnoebelen

Publication date: 16 May 2017

Published in: 2012 27th Annual IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

zbMATH Keywords

Petri netsformal verificationcomplexity theorywell-structured systemsfast-growing hierarchy

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) 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) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items (14)

Unnamed Item ⋮ The Ideal Approach to Computing Closed Subsets in Well-Quasi-orderings ⋮ Timed Basic Parallel Processes ⋮ Computable fixpoints in well-structured symbolic model checking ⋮ Ordinal recursive complexity of unordered data nets ⋮ Dynamic Networks of Timed Petri Nets ⋮ Hardness Results for Coverability Problem of Well-Structured Pushdown Systems ⋮ Unnamed Item ⋮ The ideal view on Rackoff's coverability technique ⋮ Coverability Trees for Petri Nets with Unordered Data ⋮ Linearizing well quasi-orders and bounding the length of bad sequences ⋮ Decidability Border for Petri Nets with Data: WQO Dichotomy Conjecture ⋮ The Parametric Complexity of Lossy Counter Machines ⋮ Complexity Hierarchies beyond Elementary

This page was built for publication: The Ordinal-Recursive Complexity of Timed-arc Petri Nets, Data Nets, and Other Enriched Nets