@inproceedings{91899284b23245ed8b6d3f188f9bd89c,
title = "ASERE: Assuring the satisfiability of sequential extended regular expressions",
abstract = "One purpose of Property Assurance is to check the satisfiability of properties. The Sequential Extended Regular Expressions (SEREs) play important roles in composing PSL properties. The SEREs are regular expressions with repetition and conjunction. Current assurance method for LTL formulas are not applicable to SEREs. In this paper, we present a method for checking the satisfiability of SEREs. We propose an extension of Alternating Finite Automata with internal transitions and logs of universal branches (IAFA). The new representation enables memoryful synchronization of parallel words. The compilation from SEREs to IAFAs is in linear space. An algorithm, and two optimizations are proposed for searching satisfying words of SEREs. They reduce the stepwise search space to the product of universal branches' guard sets. Experiments confirm their effectiveness.",
keywords = "Alternating Automata, Memoryful Synchronization, Satisfiability",
author = "Naiyong Jin and Huibiao Zhu",
year = "2008",
doi = "10.1007/978-3-540-88479-8\_17",
language = "英语",
isbn = "3540884785",
series = "Communications in Computer and Information Science",
publisher = "Springer Verlag",
pages = "237--251",
booktitle = "Leveraging Applications of Formal Methods, Verification and Validation - Third International Symposium, ISoLA 2008, Proceedings",
address = "德国",
}