@inproceedings{f8c0b51d4835443881cf376f4af2c59f,
title = "The tree width of auxiliary storage",
abstract = "We propose a generalization of results on the decidability of emptiness for several restricted classes of sequential and distributed automata with auxiliary storage (stacks, queues) that have recently been proved. Our generalization relies on reducing emptiness of these automata to finite-state graph automata (without storage) restricted to monadic second-order (MSO) definable graphs of bounded tree-width, where the graph structure encodes the mechanism provided by the auxiliary storage. Our results outline a uniform mechanism to derive emptiness algorithms for automata, explaining and simplifying several existing results, as well as proving new decidability results.",
keywords = "Automata, Bounded tree-width, Decision procedures, Model checking",
author = "P. Madhusudan and Gennaro Parlato",
year = "2010",
doi = "10.1145/1926385.1926419",
language = "English (US)",
isbn = "9781450304900",
series = "Conference Record of the Annual ACM Symposium on Principles of Programming Languages",
pages = "283--294",
booktitle = "POPL'11 - Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages",
note = "38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL'11 ; Conference date: 26-01-2011 Through 28-01-2011",
}