OpenNWA: A library for nested-word automata
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.
OpenNWA is a C++ implementation of NWAs, available from this website. OpenNWA provides the expected automata-theoretic operations, such as intersection, determinization, and complementation, as well as query operations. It is packaged with WALi—the Weighted Automata Library, available from the menu to the left—and interoperates closely with the weighted pushdown system portions of WALi.
- Implements (in the terminology of Alur & Madhusudan's JACM paper) linearly-accepting, weakly-hierarchical nested-word automata that fully support pending calls and returns.
- Provides the standard automata-theoretic operations, such as intersection and complement, except for minimization.
- Is extensible via a mechanism that allows the user to attach arbitrary client information to each node in the automaton.
- Inter-operates with WALi's WPDS library and allows the user to issue queries about an NWA's configuration space via the prestar and poststar functions.
- Provides extensive documentation and a test suite.
- Provides an NWA file format, readers, writers, and a set of command-line utilities for operating on file representations.