Theory and practice of symbolic automata
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.
Information and Communication Technology|
Dr. Hellis Tamm|
Dr. Hendrik Maarand
|Availability:||This position is available.|
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)|
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.
 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
 D'Antoni, L., Veanes, M.: Automata modulo theories. Commun. ACM, 64, 5, 86-95, 2021, doi: 10.1145/3419404
 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
 Brzozowski, J.A., Tamm, H.: Theory of atomata. Theor. Comput. Sci. 539, 13–27 (2014) doi: 10.1016/j.tcs.2014.04.016
 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.