Department of Intelligent Systems

Efficient Automata for Formal Reasoning

Czech title:Efektivní automaty pro formální rozhodování
Reseach leader:Holík Lukáš
Team members:Lengál Ondřej, Šimáček Jiří
Agency:Czech Science Foundation
Code:GJ16-24707Y
Start:2016-01-01
End:2018-12-31
Keywords:finite automata
formal verification
logics
decision procedures
string analysis
shape analysis
parallelism
concurrency
context-free languages
SAT
SMT

Annotation:
The project focuses on development of efficient algorithms for finite automata applicable in formal verification and analysis of dynamic systems. The central idea is to explore connections between automata, SAT/SMT solving, and program verification. We believe that because all these three domains solve similar problems, interchanging ideas between the domains is possible and may significantly advance not only the domain of automata but also the other mentioned areas. The automata-based algorithms developed in the project will in particular target the following four lively domains of applications: analysis of string manipulating programs, shape analysis, verification of concurrent programs, and decision procedures of selected logics suitable for verification of infinite-state systems (such as WSkS or separation logic). The work on the project will include rigorous mathematical description of the developed principles and algorithms, as well as their implementation and experimental evaluation.

Products

2018Sloth: An SMT Solver for String Constraints, software, 2018
Authors: Holík Lukáš, Janků Petr, Lin Anthony W., Rummer Philipp, Vojnar Tomáš
2017Gaston - Symbolic WS1S Solver, software, 2017
Authors: Fiedor Tomáš, Holík Lukáš, Janků Petr, Lengál Ondřej, Vojnar Tomáš

Publications

2018HOLÍK Lukáš, JANKŮ Petr, LIN Anthony W., RUMMER Philipp and VOJNAR Tomáš. String constraints with concatenation and transducers solved efficiently. In: Proceedings of the ACM on Programming Languages. New York: Association for Computing Machinery, 2018, pp. 96-127. ISBN 978-1-4503-5587-2.
2017ABDULLA Parosh A., ATIG Mohamed F., BUI Phi Diep, HOLÍK Lukáš, CHEN Yu-Fang, REZINE Ahmed and RUMMER Philipp. Flatten and conquer: a framework for efficient analysis of string constraints. In: Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation. New York: Association for Computing Machinery, 2017, pp. 602-617. ISBN 978-1-4503-4988-8.
 ABDULLA Parosh A., HAZIZA Frédéric, HOLÍK Lukáš, JONSSON Bengt and REZINE Ahmed. An integrated specification and verification technique for highly concurrent data structures for highly concurrent data structures. International Journal on Software Tools for Technology Transfer. 2017, vol. 5, no. 19, pp. 549-563. ISSN 1433-2779.
 FIEDOR Tomáš, HOLÍK Lukáš, JANKŮ Petr, LENGÁL Ondřej and VOJNAR Tomáš. Lazy Automata Techniques for WS1S. arXiv:1701.06282, 2017.
 FIEDOR Tomáš, HOLÍK Lukáš, JANKŮ Petr, LENGÁL Ondřej and VOJNAR Tomáš. Lazy Automata Techniques for WS1S. In: Proceedings of TACAS'17. Heidelberg: Springer Verlag, 2017, pp. 407-425. ISBN 978-3-662-54576-8. ISSN 0302-9743.
 HOLÍK Lukáš, HRUŠKA Martin, LENGÁL Ondřej, ROGALEWICZ Adam and VOJNAR Tomáš. Counterexample Validation and Interpolation-Based Refinement for Forest Automata. In: Proceedings of VMCAI'17. Cham: Springer Verlag, 2017, pp. 288-309. ISBN 978-3-319-52234-0. ISSN 0302-9743.
 HOLÍK Lukáš, MEYER Roland, VOJNAR Tomáš and WOLF Sebastian. Effect Summaries for Thread-Modular Analysis. In: SAS 2017: Static Analysis. Cham: Springer International Publishing, 2017, pp. 169-191. ISBN 978-3-319-66706-5.
 LAURENTI Luca, ABATE Alessandro, BORTOLUSSI Luca, CARDELLI Luca, ČEŠKA Milan and KWIATKOWSKA Marta. Reachability Computation for Switching Diffusions:Finite Abstractions with Certifiable and Tuneable Precision. In: Proceedings of the 20th ACM International Conference on Hybrid Systems: Computation and Control. New York: Association for Computing Machinery, 2017, pp. 55-64. ISBN 978-1-4503-4590-3.
 LENGÁL Ondřej, LIN Anthony W., MAJUMDAR Rupak and RUMMER Philipp. Fair Termination for Parameterized Probabilistic Concurrent Systems. In: Proceedings of TACAS'17. Heidelberg: Springer Verlag, 2017, pp. 499-517. ISBN 978-3-662-46680-3. ISSN 0302-9743.
 ČEŠKA Milan, ČEŠKA Milan and PAOLETTI Nicola. Precise Parameter Synthesis for Stochastic Petri Nets with Interval Rate Parameters. In: Proceedings of 16th International Conference on Computer Aided Systems Theory. Heidelberg: Springer Verlag, 2017, pp. 38-46. ISBN 978-3-319-74727-9.
2016ALDEGHERI Stefano, BARNAT Jiří, BOMBIERI Nicola, BUSATO Federico and ČEŠKA Milan. Parametric Multi-Step Scheme for GPU-Accelerated Graph Decomposition into Strongly Connected Components. In: Proceedings of 2nd Workshop on Performance Engineering for Large Scale Graph Analytics. Cham: Springer Verlag, 2016, pp. 519-531. ISBN 978-3-319-58942-8.
 ALMEIDA Ricardo, HOLÍK Lukáš and MAYR Richard. Reduction of Nondeterministic Tree Automata. In: Tools and Algorithms for the Construction and Analysis of Systems. Berlin Heidelberg: Springer Verlag, 2016, pp. 717-735. ISBN 978-3-662-49673-2.
 HOLÍK Lukáš, MEYER Roland and MUSKALLA Sebastian. Summaries for Context-Free Games. In: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2016, pp. 41-57. ISBN 978-3-95977-027-9.
 ČEŠKA Milan, PILAŘ Petr, PAOLETTI Nicola, BRIM Luboš and KWIATKOWSKA Marta. PRISM-PSY: Precise GPU-Accelerated Parameter Synthesis for Stochastic Systems. In: Proceedings of the 22nd International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Berlin: Springer International Publishing, 2016, pp. 367-384. ISBN 978-3-662-49673-2. ISSN 0302-9743.

Your IPv4 address: 23.20.223.212
Switch to IPv6 connection

DNSSEC [dnssec]