A Note on the Worst-Case Memory Requirements of Generalized Nested Depth-First Search

Reference:

Heikki Tauriainen. A note on the worst-case memory requirements of generalized nested depth-first search. Research Report A96, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo, Finland, September 2005.

Abstract:

This report presents a new nested depth-first search algorithm for testing the emptiness of a language accepted by a generalized finite Büchi automaton. Given an automaton with states, sets of accepting transitions and bits in a state descriptor, the algorithm decides whether the language accepted by the automaton is empty in at most passes of the state space, using bits of memory for the search hash table in the worst case. In addition to the standard search stacks, the algorithm also needs bits of memory for bookkeeping.

Keywords:

Büchi automata, emptiness checking, nested depth-first search

Suggested BibTeX entry:

@techreport{HUT-TCS-A96,
    address = {Espoo, Finland},
    author = {Heikki Tauriainen},
    institution = {Helsinki University of Technology, Laboratory for Theoretical Computer Science},
    month = {September},
    number = {A96},
    pages = {16},
    title = {A Note on the Worst-Case Memory Requirements of Generalized Nested Depth-First Search},
    type = {Research Report},
    year = {2005},
}