Regular Separators for VASS Coverability Languages

Chris Köcher, Georg ZetzscheFSTTCS 2023 · OpenReview

TL;DR

This paper tackles the problem of finding "regular separators" for languages generated by Vector Addition Systems with coverability semantics. The authors provide tight bounds on the size of these separators, showing that a doubly exponential-sized NFA separator always exists for disjoint VASS languages, and a triply exponential DFA separator. They also refine these bounds for specific cases like fixed dimensions and unary/binary counter updates.

What Problem Does This Paper Address?

Imagine you have two systems, each described by a Vector Addition System (VASS). These systems generate sets of possible execution sequences (languages). A crucial question in system verification is whether these two systems can never reach a state where they both perform the same sequence of actions. This is called checking for disjointness of their languages.

While it's known that two VASS languages are disjoint if and only if a "regular separator" exists (a regular language that contains one but not the other), the exact size of such separators was a mystery. Previous work established that a regular separator exists, but provided very loose upper bounds (triply exponential) and a lower bound (doubly exponential) for the size of the required automata (NFAs/DFAs). This left a significant gap and the question of whether a doubly exponential separator was always achievable. This paper aims to close that gap by precisely characterizing the size of these regular separators.

Methods

The core of the paper's contribution lies in refining the construction of regular separators. They build upon a concept called "basic separators," which are specific types of regular languages related to the behavior of VASS counters.

  1. Structural Analysis with Basic Separators: Instead of directly constructing a separator for the VASS languages, they leverage a reduction to separating a VASS language from a language representing all "safe" counter behaviors (where counters never go below zero). They then show that if a VASS language is disjoint from this "safe" language, it must be contained within a specific "basic separator" language, $B_k$. The key insight is that these basic separators are inherently deterministic, which helps avoid an exponential blow-up during complementation.
  2. Improved Complementation: The previous triply exponential upper bound arose from a complementation step. By using the structural properties of basic separators, the authors manage to avoid this costly step, leading to a doubly exponential upper bound for NFA separators.
  3. Tight Bounds and Case Analysis: The paper meticulously analyzes different scenarios:
  4. General Case: They establish a doubly exponential upper bound for NFA separators and a triply exponential bound for DFA separators.
  5. Fixed Dimension: For VASS with a fixed number of counters, they provide tighter bounds, distinguishing between unary and binary encoding of counter updates.
  6. Unary vs. Binary Encoding: They show that for unary encoding, polynomial-sized NFA separators and exponential-sized DFA separators exist. For binary encoding, this becomes exponential for NFAs and doubly exponential for DFAs.
  7. Lower Bound Constructions: To prove their upper bounds are tight, they construct specific pairs of VASS languages that require separators of the claimed sizes, using techniques that are standard in automata theory for establishing lower bounds.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and bounds for abstract language classes, not on empirical evaluation with specific datasets.

Key Insights and Ideas

  • Basic Separators are Key: The concept of "basic separators" ($B_k$) is crucial. These languages, related to counter values falling below zero, provide a structured way to analyze separability without resorting to expensive automata complementation.
  • Avoiding the Powerset Construction: The main technical achievement is finding a way to determinize automata without the standard powerset construction, which is the source of exponential blow-ups. This is achieved by exploiting the ordered nature of states in intermediate automata.
  • Tightness is Achieved: The paper successfully closes the gap between known upper and lower bounds, demonstrating that the doubly exponential size for NFA separators is indeed tight in the general case.
  • Dimension and Encoding Matter: The complexity of separators depends significantly on whether the dimension of the VASS is fixed or part of the input, and whether counter updates are encoded in unary or binary.

Key Results

  • General Case: For two disjoint d-VASS languages, there exists a separating NFA with at most doubly exponential states (in terms of dimension $d$), and a separating DFA with at most triply exponential states. These bounds are shown to be tight.
  • Fixed Dimension (Unary Encoding): For a fixed dimension $d$, separating NFAs can be polynomial in the size of the VASS, and DFAs can be exponential.
  • Fixed Dimension (Binary Encoding): For a fixed dimension $d$, separating NFAs are exponential, and DFAs are doubly exponential.
  • Special Case (1-VASS, Binary Encoding): A more efficient construction yields a separating DFA with only exponential size, rather than doubly exponential.

Limitations and Future Work

  • Focus on Coverability: The results are specific to VASS with coverability semantics. The problem of regular separability for VASS with reachability semantics remains an open problem.
  • Theoretical Bounds: The paper provides theoretical size bounds. Practical implementations might benefit from more efficient algorithms or heuristics, especially for high-dimensional VASS.
  • Generalization: While the paper extends previous work on well-structured transition systems (WSTS), further exploration of separability for other classes of WSTS could be fruitful.

Summary updated

Abstract

We study regular separators of vector addition systems (VASS, for short) with coverability semantics. A regular language R is a regular separator of languages K and L if K ⊆ R and L ∩ R = ∅. It was shown by Czerwiński, Lasota, Meyer, Muskalla, Kumar, and Saivasan (CONCUR 2018) that it is decidable whether, for two given VASS, there exists a regular separator. In fact, they show that a regular separator exists if and only if the two VASS languages are disjoint. However, they provide a triply exponential upper bound and a doubly exponential lower bound for the size of such separators and leave open which bound is tight. We show that if two VASS have disjoint languages, then there exists a regular separator with at most doubly exponential size. Moreover, we provide tight size bounds for separators in the case of fixed dimensions and unary/binary encodings of updates and NFA/DFA separators. In particular, we settle the aforementioned question. The key ingredient in the upper bound is a structural analysis of separating automata based on the concept of basic separators, which was recently introduced by Czerwiński and the second author. This allows us to determinize (and thus complement) without the powerset construction and avoid one exponential blowup.
BibTeX
@inproceedings{kocher2023regular,
  author = {Chris Köcher and Georg Zetzsche},
  title = {{Regular Separators for VASS Coverability Languages}},
  booktitle = {FSTTCS},
  year = {2023},
  url = {https://openreview.net/forum?id=tLyDeNQHIB},
}
Figure