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

DOI10.1016/J.ENTCS.2013.09.012MaRDI QIDQ265804zbMATH OpenOpenAlexWikidataFDO

Authors Uli Fahrenberg, Axel Legay

Publication date 12 April 2016

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1799498 (Why is no real title available?)
• scientific article; zbMATH DE number 4074506 (Why is no real title available?)
• scientific article; zbMATH DE number 3716792 (Why is no real title available?)
• scientific article; zbMATH DE number 17804 (Why is no real title available?)
• scientific article; zbMATH DE number 42752 (Why is no real title available?)
• scientific article; zbMATH DE number 1231616 (Why is no real title available?)
• scientific article; zbMATH DE number 1059331 (Why is no real title available?)
• scientific article; zbMATH DE number 4119653 (Why is no real title available?)
• scientific article; zbMATH DE number 821282 (Why is no real title available?)
• scientific article; zbMATH DE number 1418351 (Why is no real title available?)
• A convenient category for directed homotopy
• A theory of history dependent abstractions for learning interface automata
• Algebraic topology and concurrency
• Bisimulation from open maps
• Concurrent Machines
• Concurrent bisimulations in Petri nets
• Dipaths and dihomotopies in a cubical complex
• Formal relationships between geometrical and classical models for concurrency
• Foundations of Software Science and Computational Structures
• Generating models of infinite-state communication protocols using regular inference with abstraction
• Geometry and concurrency: a user's guide
• History-preserving bisimilarity for higher-dimensional automata via open maps
• Homotopical interpretation of globular complex by multipointed d-space
• Homotopy invariants of higher dimensional categories and concurrency in computer science
• My time with Rob
• On the expressiveness of higher dimensional automata
• Petri nets, event structures and domains. I
• The unfolding of general Petri nets
• Towards a homotopy theory of higher dimensional transition systems
• Undecidability of domino games and hhp-bisimilarity.
• Weak factorization systems and topological functors
• Weak factorizations, fractions and homotopies

Cited in

(10)

• 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
• Irrationality of process replication for higher-dimensional automata
• Hereditary History-Preserving Bisimilarity: Logics and Automata
• On symmetric higher-dimensional automata and bisimilarity
• Open Maps Bisimulations for Higher Dimensional Automata Models
• Weak morphisms of higher dimensional automata
• Partial 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)