» 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.