Towards Alternating Automata for Graph Languages


H.J. Sander Bruggink, Mathias Hülsbusch, and Barbara König. Towards alternating automata for graph languages. In Proceedings of GT-VMT 2012, Electronic Communications of the EASST, 2012.


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.

Suggested BibTeX entry:

    author = {H.J. Sander Bruggink and Mathias H{\"u}lsbusch and Barbara K{\"o}nig},
    booktitle = {Proceedings of GT-VMT 2012},
    series = {Electronic Communications of the EASST},
    title = {Towards Alternating Automata for Graph Languages},
    year = {2012}

PDF (256 kB)
© University of Duisburg-Essen, Theoretical Computer Science group