Ordinal recursive complexity of unordered data nets

DOI10.1016/J.IC.2017.02.002MaRDI QIDQ529043zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Coverability trees for Petri nets with unordered data
• The ordinal-recursive complexity of timed-arc Petri nets, data nets, and other enriched nets
• Decidability and complexity of Petri nets with unordered data
• Nets with tokens which carry data
• Nets with Tokens Which Carry Data

Cites work

• scientific article; zbMATH DE number 3677903 (Why is no real title available?)
• A Computation of the Maximal Order Type of the Term Ordering on Finite Multisets
• A classification of the expressive power of well-structured transition systems
• A well-structured framework for analysing Petri net extensions
• Algorithmic analysis of programs with well quasi-ordered domains.
• Analysis of asynchronous programs with event-based synchronization
• Complexity hierarchies beyond elementary
• Coverability trees for Petri nets with unordered data
• Decidability and complexity of Petri nets with unordered data
• Mixing Lossy and Perfect Fifo Channels
• Multiply-recursive upper bounds with Higman's lemma
• Multiset rewriting for the verification of depth-bounded processes with name binding
• Nets with tokens which carry data
• On the expressiveness of mobile synchronizing Petri nets
• Ordering by Divisibility in Abstract Algebras
• Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets
• The complexity of coverability in \(\nu\)-Petri nets
• The ordinal-recursive complexity of timed-arc Petri nets, data nets, and other enriched nets
• Unreliable channels are easier to verify than perfect channels
• Verifying programs with unreliable channels
• Well-structured transition systems everywhere!

Cited in

(7)

• The ideal view on Rackoff's coverability technique
• The Parametric Complexity of Lossy Counter Machines
• The ordinal-recursive complexity of timed-arc Petri nets, data nets, and other enriched nets
• Ordinal complexity of recursive definitions
• Parameterized broadcast networks with registers: from NP to the frontiers of decidability
• WQO dichotomy for 3-graphs
• On freeze LTL with ordered attributes

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q529043)