History-preserving bisimilarity for higher-dimensional automata via open maps

DOI10.1016/J.ENTCS.2013.09.012zbMATH Open1334.68117arXiv1209.4927OpenAlexW2081965543WikidataQ113317963 ScholiaQ113317963MaRDI QIDQ265804FDOQ265804

Axel Legay, Uli Fahrenberg

Publication date: 12 April 2016

Abstract: We show that history-preserving bisimilarity for higher-dimensional automata has a simple characterization directly in terms of higher-dimensional transitions. This implies that it is decidable for finite higher-dimensional automata. To arrive at our characterization, we apply the open-maps framework of Joyal, Nielsen and Winskel in the category of unfoldings of precubical sets.

Full work available at URL: https://arxiv.org/abs/1209.4927

Recommendations

• Open Maps Bisimulations for Higher Dimensional Automata Models
• On symmetric higher-dimensional automata and bisimilarity
• Foundations of Software Science and Computational Structures
• Hereditary History-Preserving Bisimilarity: Logics and Automata
• Partial higher-dimensional automata

zbMATH Keywords

homotopyconcurrencyhigher-dimensional automatonhistory-preserving bisimilarityunfolding

Mathematics Subject Classification ID

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

Cites Work

• Petri nets, event structures and domains. I
• Undecidability of domino games and hhp-bisimilarity.
• Weak factorization systems and topological functors
• Bisimulation from open maps
• Generating models of infinite-state communication protocols using regular inference with abstraction
• My time with Rob
• Weak factorizations, fractions and homotopies
• On the expressiveness of higher dimensional automata
• Algebraic topology and concurrency
• Dipaths and dihomotopies in a cubical complex
• Concurrent bisimulations in Petri nets
• History-preserving bisimilarity for higher-dimensional automata via open maps
• A Theory of History Dependent Abstractions for Learning Interface Automata
• Title not available (Why is that?)
• The unfolding of general Petri nets
• Homotopical interpretation of globular complex by multipointed d-space
• Concurrent Machines
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Geometry and concurrency: a user's guide
• Homotopy invariants of higher dimensional categories and concurrency in computer science
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Formal Relationships Between Geometrical and Classical Models for Concurrency
• Towards a homotopy theory of higher dimensional transition systems
• A convenient category for directed homotopy
• Foundations of Software Science and Computational Structures

Cited In (7)

• Spaces of directed paths on pre-cubical sets II
• History-preserving bisimilarity for higher-dimensional automata via open maps
• ST-structures
• Weighted and branching bisimilarities from generalized open maps
• Hereditary History-Preserving Bisimilarity: Logics and Automata
• Open Maps Bisimulations for Higher Dimensional Automata Models
• Weak morphisms of higher dimensional automata

This page was built for publication: History-preserving bisimilarity for higher-dimensional automata via open maps

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