Knihovna pro práci s restartovacími automaty

• Thesis title in Czech: Knihovna pro práci s restartovacími automaty
• Thesis title in English: A library for working with restarting automata
• Key words: restartovací automaty|Python|formální jazyky
• English key words: restarting automaton|Python|formal langugaes
• Academic year of topic announcement: 2020/2021
• Thesis type: Bachelor's thesis
• Thesis language: čeština
• Department: Department of Software and Computer Science Education (32-KSVI)
• Supervisor: RNDr. František Mráz, CSc.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 23.03.2021
• Date of assignment: 23.03.2021
• Confirmed by Study dept. on: 13.04.2021

Guidelines

Restarting automata are formal automata introduced for modeling the so-called reduction analysis of natural languages. The model is non-classical and exists in many variants, mainly as a theoretical tool. The thesis's goal is to implement a software tool in the form of a Python library for experimenting with restarting automata. The library should enable a straightforward design, simulation, storing, and testing of diverse types of restarting automata. The proposed use of the library will be testing new restarting automata and verifying that automata in published or prepared articles are correct. The emphasis will be put on easy-to-use functions and extensibility, but not the efficiency of the simulation. The library should support its extensions to other known or future versions of restarting automata. Additionally, the library should enable to check some simple properties like determinism of a given automaton and at least one non-trivial property like monotonicity of a given automaton.

A selected subset of the functionality of the library will be accessible via web presentation of restarting automata that enables to design and simulate such automata in a web page.

References

Otto, F. (2006). Restarting Automata. Recent Advances in Formal Languages and Applications, 25, 269-303.

Jančar, P., Mráz, F., Plátek, M., & Vogel, J. (1999). On monotonic automata with a restart operation. Journal of Automata, Languages and Combinatorics, 4(4), 287-311.

Almeida, A., Almeida, M., Alves, J., Moreira, N., & Reis, R. (2009). FAdo and GUItar: tools for automata manipulation and visualization. In International Conference on Implementation and Application of Automata (pp. 65-74). Springer, Berlin, Heidelberg.