OpenNWA: A Nested-Word Automaton Library

Driscoll, Evan and Thakur, Aditya V. and Reps, Thomas W.
24th International Conference on Computer Aided Verification (CAV), 2012

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.

PDF     Springer©    

@inproceedings{driscoll_etal_CAV12,
  author = {Driscoll, Evan and Thakur, Aditya V. and Reps, Thomas W.},
  title = {OpenNWA: {A} Nested-Word Automaton Library},
  booktitle = {24th International Conference on Computer Aided Verification ({CAV})},
  year = {2012},
  pages = {665--671},
  publisher = {Springer},
  doi = {10.1007/978-3-642-31424-7_47}
}