Trace language

In theoretical computer science , a trace language is a formal language that models processes that can be carried out in parallel. The letters of a given alphabet are viewed as elementary operations that influence one another in their execution (ie they are dependent) or can be independent of one another. A word in this language corresponds to the successive execution of these operations, i.e. a program.

Two words above this alphabet (i.e. two programs) are considered indistinguishable if they can only be converted into one another by exchanging independent letters next to one another (possibly several times), i.e. ultimately describing the same algorithm.

definition

Let be an alphabet and a binary, symmetric and reflexive relation , called the dependency relation. They say and are independent, if . ${\displaystyle \Sigma }$ ${\displaystyle D\subseteq \Sigma \times \Sigma }$ ${\displaystyle \Sigma }$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle (a,b)\not \in D}$

Then one defines as the smallest equivalence relation for which applies ${\displaystyle \sim _{D}}$

${\displaystyle xaby\sim _{D}xbay\iff (a,b)\not \in D}$for everyone . ${\displaystyle x,y\in \Sigma ^{*},a,b\in \Sigma }$

The equivalence classes below are known as Mazurkiewicz spuren. ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \sim _{D}}$

Since there is a congruence relation below the concatenation , a monoid noted as forms the monoid of the tracks. ${\displaystyle \sim _{D}}$ ${\displaystyle \Sigma _{/\sim _{D}}^{*}}$ ${\displaystyle \mathbb {M} (\Sigma ,D)}$

Subsets of are then referred to as lane languages. ${\displaystyle \mathbb {M} }$

Recognizability

Special trace languages, like formal languages, can be recognized by automata. Asynchronous cellular automata are used for this.