Files in this item

FilesDescriptionFormat

application/pdf

application/pdfgraphautomata-tr.pdf (249kB)
(no description provided)PDF

Description

Title:The Tree Width of Automata with Auxiliary Storage
Author(s):Madhusudan, P.
Contributor(s):Parlato, Gennaro
Subject(s):automata, auxiliary storage, tree-width, emptiness, decidability
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) 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.
Issue Date:2010
Genre:Technical Report
Type:Text
Language:English
URI:http://hdl.handle.net/2142/15433
Publication Status:unpublished
Peer Reviewed:not peer reviewed
Date Available in IDEALS:2010-04-28


This item appears in the following Collection(s)

Item Statistics