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.


If you have any questions, email the wali-users mailing list, shared with OpenNWA. (Alternatively, you can try Evan Driscoll or Aditya Thakur.)