The Tree Width of Automata with Auxiliary Storage

Madhusudan, P.

Permalink

https://hdl.handle.net/2142/15433 Copy

Description

Title

The Tree Width of Automata with Auxiliary Storage

Author(s)

Madhusudan, P.

Contributor(s)

Parlato, Gennaro

Issue Date

2010

Keyword(s)

automata, auxiliary storage, tree-width, emptiness, decidability

Date of Ingest

2010-04-28T05:45:16Z

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.

Type of Resource

text

Genre of Resource

Technical Report

Language

en

Permalink

http://hdl.handle.net/2142/15433

Owning Collections