Specification and Evaluation of an Efficient Recognizer for Rational Trace Languages

Abstract

An improved, one-pass version of a two-pass, Earley-like recognition algorithm is here proposed to solve the Membership Problem for rational trace languages in polynomial time. The algorithm is first described through the formal specification of what we called a Non Deterministic Buffer Machine (NDBM); secondly, the recognition is detailed through a deterministic algorithm along with some running examples. In addition, we describe our prototype implementation of the algorithm used to empirically evaluate the performances and the characteristics of the proposed solution. To this end, we designed pseudo-random testing data generators that are here described as well.