Teme teorijskih seminara iz MTR-a

(Napomena: Sa zvjezdicom [*] su označeni dodatni teži dijelovi koji nisu obavezan dio seminara)

Dobro utemeljene relacije i dobri parcijalni uređaji

[preuzeo Davor Borojevic]

• Ograda na ordinalnu dubinu tranzitivne relacije pokrivene dobro utemeljenim relacijama (Teorem 5)
• [*] Precizna karakterizacija u terminima produkta ordinalnih dubina dobro utemeljenih relacija (Teorem 6)

Reference:

1. A. Blass, Y. Gurevich: Program Termination, and Well Partial Ordering, Tech report MSR-TR-2006-27, Microsoft Research, March 2006.

Brzi algoritam za prepoznavanje riječi opisanih regularnim izrazima

[preuzeo Aleksandar Uscumlic]

• Sekcije 2 i 4 iz [1]
• [*] Usporedba s algoritmom opisanim u [2]

Reference:

1. P. Bille, M. Farach-Colton: Fast and Compact Regular Expression Matching, Submitted, 2006.
2. P. Bille: New Algorithms for Regular Expression Matching, ICALP (1) 2006: 643-654.

Dvosmjerni i višetračni automati

[preuzeo Martin Ferlan]

• Dvosmjerni automati; redukcija na jednosmjerne automate (Rabin-Scottov [1] i Shepherdsenov [2] dokaz)
• Svojstva višetračnih automata

Reference:

1. M. O. Rabin, D. Scott: Finite automata and their decision problems, IBM Journal of Research and Development 3: 114-125 (1959).
2. J. C. Shepherdson: The reduction of two-way automata to one-way automata, IBM Journal of Research and Development 3: 198-200 (1959).

Dvodimenzionalni jezici

[preuzeo Marijan Polic]

• Svojstva i odnosi nekoliko modela automata za prepoznavanje dvodimenzionalnih jezika
• [*] Odnos prema sustavima popločavanja i sustavima domina

Reference:

1. D. Giammarresi, A. Restivo: Two-dimensional languages, Handbook of Formal Languages, Vol 3, 1997, 215-267.

Alternirajući automati i aperiodički jezici

[preuzeo Damjan Namjesnik]

• Konstrukcija alternirajućeg automata iz proširenog regularnog izraza
• Konstrukcija alternirajućeg automata bez petlji iz proširenog regularnog izraza bez iteracije

Reference:

1. K. Salomaa, S. Yu: Alternating finite automata and star-free languages, Theoretical Computer Science 234(1-2): 167-176 (2000).

Automati listova

• Svojstva automata listova obzirom na prihvaćajuće uvjete zadane formalnim jezikom
• [*] Svojstva automata listova obzirom na prihvaćajuće uvjete zadane klasom složenosti

Reference:

1. T. Peichl, H. Vollmer: Finite Automata with Generalized Acceptance Criteria. Discrete Mathematics & Theoretical Computer Science 4(2): 179-192 (2001).

Uklopljene riječi

[preuzeo Srdjan Romcevic]

• Automati za prepoznavanje uklopljenih riječi i osnovni rezultati [1]
• Ekvivalencija klasa regularnih jezika uklopljenih riječi i klase kontekstno slobodnih jezika [2]

Reference:

1. R. Alur, P. Madhusudan: Adding Nesting Structure to Words, Developments in Language Theory 2006: 1-13.
2. A. Blass, Y. Gurevich: A Note on Nested Words, Tech report MSR-TR-2006-139, Microsoft Research, October 2006.

Vidljivo potisni automati

• Svojstva vidljivo potisnih automata [1]
• [*] Nalaženje minimalnih vidljivo potisnih automata [2]

Reference:

1. R. Alur, P. Madhusudan: Visibly pushdown languages, STOC 2004: 202-211.
2. R. Alur, V. Kumar, P. Madhusudan, M. Viswanathan: Congruences for Visibly Pushdown Languages, ICALP 2005: 1102-1114.

Determinizacija nedeterminističkih Büchijevih automata

• Osnovni tipovi omega-automata
• Safrina konstrukcija za determinizaciju nedeterminističkih Büchijevih automata

Reference:

1. B. Farwer: omega-Automata, In: Automata, Logics, and Infinite Games, LNCS 2500, Springer, 2002, 3-20. [dostupno u obliku fotokopije]
2. M. Roggenbach: Determinization of Büchi-Automata, In: Automata, Logics, and Infinite Games, LNCS 2500, Springer, 2002, 43-60.

Vremenski regulirani automati

[preuzela Danijela Peric]

• Modeli vremenski reguliranih automata, primjeri, osnovna svojstva vremenskih reguliranih jezika; provjera nepraznosti
• [*] Neodlučiva svojstva vremenski reguliranih automata

Reference:

1. R. Alur, D. L. Dill: A Theory of Timed Automata. Theoretical Computer Science 126(2): 183-235 (1994).

Teme teorijskih seminara odabrao: Matko Botinčan.