The tree width of auxiliary storage

P. Madhusudan, Gennaro Parlato

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Pages (from-to)283-294
Number of pages12
JournalACM SIGPLAN Notices
Volume46
Issue number1
DOIs
StatePublished - Jan 2011

Keywords

  • Automata
  • Bounded tree-width
  • Decision procedures
  • Model checking

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'The tree width of auxiliary storage'. Together they form a unique fingerprint.

Cite this