Languages of higher-dimensional automata
From MaRDI portal
Publication:5076390
Simplicial sets, simplicial objects (18N50) Linearly ordered topological spaces, generalized ordered spaces, and partially ordered spaces (54F05) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)
Abstract: We introduce languages of higher-dimensional automata (HDAs) and develop some of their properties. To this end, we define a new category of precubical sets, uniquely naturally isomorphic to the standard one, and introduce a notion of event consistency. HDAs are then finite, labeled, event-consistent precubical sets with distinguished subsets of initial and accepting cells. Their languages are sets of interval orders closed under subsumption; as a major technical step we expose a bijection between interval orders and a subclass of HDAs. We show that any finite subsumption-closed set of interval orders is the language of an HDA, that languages of HDAs are closed under binary unions and parallel composition, and that bisimilarity implies language equivalence.
Recommendations
- scientific article; zbMATH DE number 2143010
- On the expressiveness of higher dimensional automata
- scientific article; zbMATH DE number 18280
- On the specification of higher dimensional automata
- scientific article; zbMATH DE number 53545
- scientific article; zbMATH DE number 130894
- Higher dimensional automata revisited
- Partial higher-dimensional automata
- On the expressiveness of higher dimensional automata (extended abstract)
- Foundations of Software Science and Computational Structures
Cites work
- A cubical model of homotopy type theory
- Algebraic topology and concurrency
- An algebraic characterization of the behaviour of non-sequential systems
- Bisimulation from open maps
- Computer science today. Recent trends and developments
- Concurrent Machines
- Configuration structures, event structures and Petri nets
- Dipaths and dihomotopies in a cubical complex
- Directed algebraic topology and concurrency. With a foreword by Maurice Herlihy and a preface by Samuel Mimram
- Directed algebraic topology. Models of non-reversible worlds
- Erratum to ``On the expressiveness of higher dimensional automata
- Failures semantics based on interval semiwords is a congruence for refinement
- Foundations of Software Science and Computational Structures
- Generating Posets Beyond N
- Higher dimensional automata revisited
- Homologie singulière des espaces fibrés. Applications
- scientific article; zbMATH DE number 6694181 (Why is no real title available?)
- scientific article; zbMATH DE number 3877239 (Why is no real title available?)
- scientific article; zbMATH DE number 3735177 (Why is no real title available?)
- scientific article; zbMATH DE number 42752 (Why is no real title available?)
- scientific article; zbMATH DE number 1216133 (Why is no real title available?)
- scientific article; zbMATH DE number 1927576 (Why is no real title available?)
- scientific article; zbMATH DE number 2143010 (Why is no real title available?)
- scientific article; zbMATH DE number 1924514 (Why is no real title available?)
- Intransitive indifference with unequal indifference intervals
- Modeling concurrency with interval traces
- Modeling concurrency with partial orders
- Models for concurrency: Towards a classification
- Modular construction and partial order semantics of Petri nets
- On interprocess communication. I: Basic formalism
- On the expressiveness of higher dimensional automata
- Petri nets, event structures and domains. I
- Refinement of actions and equivalence notions for concurrent systems
- Sculptures in concurrency
- Spaces of directed paths on pre-cubical sets
- Spaces of directed paths on pre-cubical sets II
- ST-structures
- Structure of concurrency
- The equational theory of pomsets
- The mutual exclusion problem
- The univalence axiom in cubical sets
- Transition and cancellation in concurrency and branching time
Cited in
(30)- Feedback automata and their languages
- Languages, D0L-systems, sets of curves, and surface automorphisms.
- Trees in partial higher dimensional automata
- Labeled homology of higher-dimensional automata
- On the expressiveness of higher dimensional automata
- Posets with interfaces as a model for concurrency
- On the specification of higher dimensional automata
- Modal logic over higher dimensional automata
- scientific article; zbMATH DE number 18280 (Why is no real title available?)
- scientific article; zbMATH DE number 1497799 (Why is no real title available?)
- Higher dimensional automata revisited
- scientific article; zbMATH DE number 2143010 (Why is no real title available?)
- scientific article; zbMATH DE number 1372681 (Why is no real title available?)
- Convolution and concurrency
- Partial higher-dimensional automata
- Foundations of Software Science and Computational Structures
- A Myhill-Nerode theorem for higher-dimensional automata
- Regular planar monoidal languages
- A Kleene theorem for higher-dimensional automata
- Closure and decision properties for higher-dimensional automata
- Myhill-Nerode theorem for higher-dimensional automata
- Presheaf automata
- Higher catoids, higher quantales and their correspondences
- Bisimulations and logics for higher-dimensional automata
- Closure and decision properties for higher-dimensional automata
- Irrationality of process replication for higher-dimensional automata
- Presenting interval pomsets with interfaces
- Kleene theorem for higher-dimensional automata
- Logic and languages of higher-dimensional automata
- Compositional control-driven Boolean circuits
This page was built for publication: Languages of higher-dimensional automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5076390)
