Don't Care Words with an Application to the Automata-based Approach for Real Addition

Jochen Eisinger and Felix Klaedtke

Automata are a useful tool in infinite state model checking,since they can represent infinite sets of integers and reals. However, analogous to BDDs to represent finite sets, an obstacle of an automata-based set representation is the sizes of the automata. In this paper, we generalizethe notion of "don't cares" for BDDs to word languages as a means to reduce the automata sizes. A general result in this paper shows that the minimal weak deterministic Büchi automaton (WDBA) with respect to a given don't care set with certain restrictions is uniquely determined and can be efficiently constructed. We apply don't cares to mechanize amore effective decision procedure for the first-order logic over the mixed linear arithmetic over the integers and the reals based on WDBAs.

back