Master's Thesis web

Operational state complexity of union, intersection, and concatenation over unary automata with half of the states final

Thesis Supervisor: RNDr. Juraj Šebej, PhD.

Analysis and proposal of the thesis solution

program implementation, obtained statistics, some hypotheses

Extended abstract

proposed at the end of the first semester

Presentation SDIa

recapitulation of implementation and hypotheses

Final presentation

Student Scientific Conference

Objectives

1
To study known results of operations union, intersection and concatenation over general alphabet and unary alphabet.

2
Create a program which generate unary automata and can realize mentioned operation over two automata. Use program to obtain basic statistical results and formulate hypotheses for lower bounds of operational state complexities.

3
Generalize obtained hypotheses from 2, and prove their tightness.

Bibliography

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to automata theory, languages, and computation - international edition (2. ed). Addison-Wesley (2003)

Jacques Sakarovitch: Elements of Automata Theory. Cambridge University Press 2009, ISBN 978-0-521-84425-3, pp. I-XXIV, 1-758 (2009)

Marek Hricko, Galina Jirásková, Alexander Szabari: Union and Intersection of Regular Languages and Descriptional Complexity. DCFS 2005: 170-181
contact: petra.plskova [at] student.upjs.sk