Towards Alternating Automata for Graph Languages

H.J. Sander Bruggink, Mathias Hülsbusch, Barbara König


In this paper we introduce alternating automata for languages of arrows of an arbitrary category, and as an instantiation thereof alternating automata for graph languages. We study some of their closure properties and compare them, with respect to expressiveness, to other methods for describing graph languages. We show, by providing several examples, that many graph properties (of graphs of bounded path width) can be naturally expressed as alternating automata.

Full Text:




Hosted By Universitätsbibliothek TU Berlin.