Standard automata, such as Kleene automata and omega-automata, model the behavior of sequential systems with finite memory. They allow systems to be described in multiple ways using various mathematical objects such as logic and rational expressions. Standard automata, such as Kleene automata and omega-automata, model the behavior of sequential systems with finite memory. They allow systems to be described in multiple ways using various mathematical objects such as logic and rational expressions. This allows to observe system behavior from multiple perspectives and describe it in multiple ways in order to study its properties.

Higher-dimensional automata (HDAs), first explored from a geometric and topological perspective, have more recently attracted attention from the standpoint of language theory, to which the Automata and Applications group is contributing.

HDAs model concurrent events through overlapping intervals, interfaces to glue them. They are automata in which concurrency is modeled using higher-dimensional structures: squares, cubes, etc. Their languages do not consist of words (sequences or totally ordered sets of symbols) but rather of partially ordered multisets of symbols (pomsets with interfaces) [1]:

• the elements are intervals describing the duration of an event's activity, where two events are concurrent if and only if their intervals overlap
• interfaces describe parts of intervals that are not started or are not terminated

In the Automata and applications group we are developing the foundations of higher-dimensional automata theory:

• the language theory of HDAs (Kleene theorem [2]; Myhill-Nerode theorem [3]; Büchi-Elgot-Trakhtenbrot theorem [4]; etc.)
• extensions of HDAs (higher-dimensional timed automata [5]; HDAs on ω-words; etc.)
• logics for HDAs (monadic second-order logic; linear temporal logic; branching-time logics [6]; etc.)
• relations to other formalisms for concurrent and distributed systems (Petri nets [7]; communicating automata; etc.)

Related Publications