A one-pass recognition algorithm is presented to solve the membership problem for rational trace languages. The algorithm 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. The performances and characteristics of the proposed solution are evaluated on a testbed implementation using pseudo-random traces, strings, languages and dependency relations.
@inproceedings{Maggi2014A_Recognizer,
title = {{A Recognizer of Rational Trace Languages}},
author = {Maggi, Federico},
booktitle = {Proceedings of the 10th International Conference on Computer and Information Technology},
series = {CIT},
month = {June},
year = {2010},
isbn = {978-0-7695-4108-2},
pages = {257--264},
publisher = {IEEE Computer Society}
}