Department of Intelligent Systems

Efficient Automata for Formal Reasoning

Czech title:Efektivní automaty pro formální rozhodování
Research leader:Holík Lukáš
Team members:Lengál Ondřej, Šimáček Jiří
Agency:Czech Science Foundation
Keywords:finite automata
formal verification
decision procedures
string analysis
shape analysis
context-free languages

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.


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áš


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:
Switch to IPv6 connection

DNSSEC [dnssec]