Ordinal recursive complexity of unordered data nets

DOI10.1016/J.IC.2017.02.002zbMATH Open1370.68219OpenAlexW2591668504MaRDI QIDQ529043FDOQ529043

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

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

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)

Cites Work

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

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)