Minimization of Visibly Pushdown Automata Using Partial Max-SAT

We consider the problem of state-space reduction for nondeterministic weakly-hierarchical visibly pushdown automata (VPA). VPA recognize a robust and algorithmically tractable fragment of context-free languages that is natural for modeling programs. We define an equivalence relation that is sufficie...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2017-04
Main Authors: Heizmann, Matthias, Schilling, Christian, Tischner, Daniel
Format: Article
Language:English
Subjects:
Algorithms
Boolean algebra
Context free languages
Equivalence
Optimization
Program verification (computers)
Reduction
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the problem of state-space reduction for nondeterministic weakly-hierarchical visibly pushdown automata (VPA). VPA recognize a robust and algorithmically tractable fragment of context-free languages that is natural for modeling programs. We define an equivalence relation that is sufficient for language-preserving quotienting of VPA. Our definition allows to merge states that have different behavior, as long as they show the same behavior for reachable equivalent stacks. We encode the existence of such a relation as a Boolean partial maximum satisfiability (PMax-SAT) problem and present an algorithm that quickly finds satisfying assignments. These assignments are sub-optimal solutions to the PMax-SAT problem but can still lead to a significant reduction of states. We integrated our method in the automata-based software verifier Ultimate Automizer and show performance improvements on benchmarks from the software verification competition SV-COMP.
ISSN:2331-8422
DOI:10.48550/arxiv.1701.05160