A Recognizer of Rational Trace Languages

The relevance of instruction parallelization and optimal event scheduling is currently increasing. In particular, because of the high amount of computational power available today, the industrial interest on automatic code parallelization is raising notably. In the last years, several contributions have arisen in these fields, exploiting the theory of traces that provides a powerful mathematical formalism that can be effectively used to model and study concurrent executions of events. However, there is a quite large amount of open problems that need to be further investigated in this area. In this paper, we present a one-pass recognition algorithm to solve the membership problem for rational trace languages, that is the problem of deciding whether or not a certain string belongs (i.e., is member of) a trace, or a trace language. Solving this problem is fundamental for designing efficient parsers. Our solution is detailed through the formal specification of the Buffer Machine, a non-deterministic, finite-state automaton with multiple buffers that can solve the membership problem in polynomial time.