OpenNWA: A Nested-Word Automaton Library
Evan Driscoll, Aditya Thakur, and Thomas Reps
Nested-word automata (NWAs) are a language formalism that helps bridge
the gap between finite-state automata and pushdown automata. NWAs can
express some context-free properties, such as parenthesis matching,
yet retain all the desirable closure characteristics of finite-state
automata.
This paper describes OpenNWA, a C++ library for working with NWAs.
The library provides the expected automata-theoretic operations, such
as intersection, determinization, and complementation. It is packaged
with
WALi—the Weighted Automaton Library—and
interoperates closely with the weighted pushdown system portions of
WALi.
(Click here to access the paper:
PDF;
(c) Springer-Verlag.)
University of Wisconsin