Ordinal recursive complexity of unordered data nets

DOI10.1016/j.ic.2017.02.002zbMath1370.68219OpenAlexW2591668504MaRDI QIDQ529043

Fernando Rosa-Velardo

Publication date: 18 May 2017

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2017.02.002

zbMATH Keywords

data netsfast-growing complexity hierarchyhyper-Ackermannian problemsmultisets over \(\mathbb{N}^k\)ordinal recursive complexity

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Complexity of computation (including implicit computational complexity) (03D15) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Hierarchies of computability and definability (03D55)

Related Items (4)

WQO dichotomy for 3-graphs ⋮ The ideal view on Rackoff's coverability technique ⋮ On Freeze LTL with Ordered Attributes ⋮ The Parametric Complexity of Lossy Counter Machines

Cites Work

• Unnamed Item
• Unnamed Item
• A classification of the expressive power of well-structured transition systems
• Decidability and complexity of Petri nets with unordered data
• Multiset rewriting for the verification of depth-bounded processes with name binding
• A well-structured framework for analysing Petri net extensions
• Algorithmic analysis of programs with well quasi-ordered domains.
• Unreliable channels are easier to verify than perfect channels
• Verifying programs with unreliable channels
• Analysis of Asynchronous Programs with Event-Based Synchronization
• Coverability Trees for Petri Nets with Unordered Data
• Complexity Hierarchies beyond Elementary
• On the Expressiveness of Mobile Synchronizing Petri Nets
• The Ordinal-Recursive Complexity of Timed-arc Petri Nets, Data Nets, and Other Enriched Nets
• Multiply-Recursive Upper Bounds with Higman’s Lemma
• Mixing Lossy and Perfect Fifo Channels
• A Computation of the Maximal Order Type of the Term Ordering on Finite Multisets
• Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets
• The Complexity of Coverability in ν-Petri Nets
• Ordering by Divisibility in Abstract Algebras
• Well-structured transition systems everywhere!

This page was built for publication: Ordinal recursive complexity of unordered data nets