A classification of the expressive power of well-structured transition systems

DOI10.1016/j.ic.2010.11.003zbMath1217.68146OpenAlexW2090757722MaRDI QIDQ553290

Laurent Van Begin, Parosh Aziz Abdulla, Giorgio Delzanno

Publication date: 27 July 2011

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

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

zbMATH Keywords

expressivenesslanguage theorywell-structured transition systems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Grammars and rewriting systems (68Q42)

Related Items

Unnamed Item ⋮ Ordinal recursive complexity of unordered data nets ⋮ Decidability and complexity of Petri nets with unordered data ⋮ Petri nets with name creation for transient secure association ⋮ Complexity Hierarchies beyond Elementary ⋮ Well-quasi-ordering hereditarily finite sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Undecidable verification problems for programs with unreliable channels
• A well-structured framework for analysing Petri net extensions
• Unreliable channels are easier to verify than perfect channels
• Verifying programs with unreliable channels
• On the \(\omega\)-language expressive power of extended Petri nets
• Well-structured languages
• Comparing the Expressive Power of Well-Structured Transition Systems
• Nets with Tokens Which Carry Data
• Name Creation vs. Replication in Petri Net Systems
• Deciding properties of integral relational automata
• A classification of symbolic transition systems
• Well-structured transition systems everywhere!