Symbolic WS1S

Loris D'Antoni, Margus Veanes

Abstract

Weak Monadic Second-Order Logic of One Successor (WS1S) is a powerful, decidable logic used for reasoning about sequences. However, its traditional reliance on finite alphabets limits its applicability to real-world data streams like integer sequences or Unicode text. This paper introduces Symbolic WS1S (s-WS1S), an extension that allows for infinite alphabets by leveraging symbolic automata and effective Boolean algebras. We present two decision procedures for s-WS1S—one based on symbolic finite automata and another using minterm reductions to standard WS1S—proving that expressive reasoning over complex data remains decidable.

1. Introduction

In computer science, reasoning about sequences of events—such as program execution traces or strings of text—is a fundamental task. WS1S has long been a standard tool for this purpose due to its decidability. However, when dealing with infinite domains (e.g., sequences of integers), standard WS1S requires manual "abstractions" that simplify data into finite labels, often losing critical information. Symbolic WS1S (s-WS1S) addresses this by allowing formulas to natively handle predicates from any decidable first-order theory, such as linear integer arithmetic.

2. Methodology

The authors propose two distinct decision procedures to determine the satisfiability of s-WS1S formulas:

2.1 Reduction to Symbolic Finite Automata (s-FA)

Standard WS1S solving typically involves converting formulas into finite automata. The authors extend this by using Symbolic Finite Automata, where transitions are labeled with predicates rather than single characters. To facilitate this, they define a Cartesian Product Algebra that combines "position-predicates" (tracking sequence indices) with "character-predicates" (the actual data at those positions). This framework is implemented using Binary Decision Trees (BDTs) for computational efficiency.

2.2 Reduction to Standard WS1S via Minterms

This approach recognizes that for any specific formula, only a finite number of predicates are relevant, even if the underlying alphabet is infinite. By calculating the minterms—the smallest non-overlapping Boolean combinations of these predicates—the authors can map the complex symbolic problem back into a standard WS1S problem over a finite alphabet. This allows the use of existing high-performance WS1S solvers.

3. Key Insights

  • Effective Boolean Algebras: The decidability of s-WS1S hinges on the underlying alphabet theory forming an Effective Boolean Algebra. If one can perform basic Boolean operations and check for satisfiability within the alphabet theory, the entire sequence logic remains decidable.
  • Parametric Expressivity: s-WS1S is parametric, meaning users can swap alphabet theories (e.g., linear arithmetic for integers, bit-vector logic for hardware) without changing the core logic framework.
  • The Power of Minterms: The ability to "collapse" an infinite alphabet into a finite set of equivalence classes (minterms) provides a critical bridge between symbolic and classical logic.

4. Results and Limitations

The paper successfully defines the syntax and semantics for s-WS1S and provides formal proofs of its decidability. While s-WS1S is strictly more expressive than standard WS1S and avoids the exponential blow-up associated with manual abstraction, it faces its own challenges. The reduction via minterms can cause an exponential increase in the alphabet size relative to the number of distinct predicates, which may impact performance for complex formulas.

5. Future Work

As this is a theoretical presentation, the authors identify several avenues for future research, including a comprehensive empirical evaluation of the proposed algorithms. They also suggest investigating whether existing heuristics from established tools like MONA can be adapted to the symbolic setting to improve practical performance.

Summary updated

BibTeX
@inproceedings{dantoni2015symbolic,
  author = {Loris D'Antoni and Margus Veanes},
  title = {{Symbolic WS1S}},
  booktitle = {LPAR (short Papers)},
  year = {2015},
  doi = {10.29007/t28j},
}
Figure