Please use this identifier to cite or link to this item:
Title: The Tree Width of Automata with Auxiliary Storage
Keywords: automata, auxiliary storage, tree-width, emptiness, decidability
Issue Date: 2010
Description: 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) defined on monadic second-order (MSO) definable graphs of bounded treewidth, 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 theorems.;unpublished;not peer reviewed
Type Of Material: OTHER
Appears in Collections:College of Engineering

Files in This Item:
Click on the URI links for accessing contents.

Items in HannanDL are protected by copyright, with all rights reserved, unless otherwise indicated.