Towards Alternating Automata for Graph Languages
Reference
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.
Abstract
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:
@inproceedings{bhk:alternating2012,
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}
}
