Theory and practice of symbolic automata
» Apply now PDF Show all positions
Abstract
Symbolic finite automata extend classical automata by allowing infinite alphabets. This PhD project explores theoretical as well as practical aspects of symbolic automata, and the role of atoms of regular languages for the automata in the symbolic setting.
| Research field: |
Information and communication technology |
|---|---|
| Supervisors: |
Dr. Hellis Tamm Dr. Hendrik Maarand |
| Availability: | This position is available. |
| Offered by: |
School of Information Technologies Department of Software Science |
| Application deadline: | Applications are accepted between September 01, 2021 00:00 and September 30, 2021 23:59 (Europe/Zurich) |
Description
Symbolic finite automata [1,2] extend classical automata by allowing infinite alphabets. Indeed *predicates* over such alphabets, which form a Boolean algebra, serve as labels of transitions. Symbolic automata have been studied intensively in recent years, because they solve some practical problems for which classical finite automata are unsuitable. However, the study of symbolic automata is a young field and much work is still to be done. This PhD project explores theoretical as well as practical aspects of symbolic automata. The project will advance symbolic automata research, studying classes of finite automata (e.g. residual automata, reversible automata, boolean automata) in the symbolic setting [3,5]. Also, the role of atoms of regular languages [4,5] in the symbolic setting will be explored.
[1] D’Antoni, L., Veanes, M.: The power of symbolic automata and transducers. CAV 2017. LNCS 10426, 47–67, Springer. doi: 10.1007/978-3-319-63387-9_3
[2] D'Antoni, L., Veanes, M.: Automata modulo theories. Commun. ACM, 64, 5, 86-95, 2021, doi: 10.1145/3419404
[3] Stanford, C., Veanes, M., Bjørner, N.: Symbolic Boolean derivatives for efficiently solving extended regular expression constraints. PLDI 2021, 620--635, ACM. doi: 10.1145/3453483.3454066
[4] Brzozowski, J.A., Tamm, H.: Theory of atomata. Theor. Comput. Sci. 539, 13–27 (2014) doi: 10.1016/j.tcs.2014.04.016
[5] Tamm, H., Veanes, M.: Theoretical aspects of symbolic automata. SOFSEM 2018. LNCS 10706, 428-441, Springer. doi: 10.1007/978-3-319-73117-9_30
Applicants should be highly motivated and ideally have some previous knowledge of automata theory.