The tree width of auxiliary storage

The tree width of auxiliary storage,10.1145/1925844.1926419,Sigplan Notices,P. Madhusudan,Gennaro Parlato

The tree width of auxiliary storage   (Citations: 2)
BibTex | RIS | RefWorks Download
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.
Journal: Sigplan Notices - SIGPLAN , pp. 283-294, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...The model of nested word automata has been recently extended to more general graph automata by Madhusudan and Parlato [22]...
    • ...In the same way as an inputdriven pushdown automaton can be simulated by a finite automaton operating on nested words, other types of machines with auxiliary storage can be realized by finite graph automata working on specialized graphs, and the structure of the graphs allows one to obtain decidability results for the corresponding auxiliary storage model [22]...

    Alexander Okhotinet al. Descriptional Complexity of Unambiguous Nested Word Automata

    • ...It is known that looking at the computations as nested words with multiple stack relations, when restricting to k-context computations, the corresponding set has a bounded tree-width (see [12])...

    Salvatore La Torreet al. Reachability of Multistack Pushdown Systems with Scope-Bounded Matchin...

Sort by: