publication . Part of book or chapter of book . 2006

Symbolic implementation of alternating automata

Alessandro Cimatti; Marco Roveri;
Restricted
  • Published: 09 Aug 2006
  • Publisher: Springer Berlin Heidelberg
Abstract
We show how to convert alternating Buechi automata to symbolic structures, using a variant of Miyano and Hayashi’s construction. We avoid building the nondeterministic equivalent of the alternating automaton, thus save an exponential factor in space. For one-weak automata, Miyano and Hayashi’s approach produces automata that are larger than needed. We show a hybrid approach that produces a smaller nondeterministic automaton if part of the alternating automaton is one weak. We perform a thorough experimental analysis and conclude that the symbolic approach outperforms the explicit one.
Download from
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue