Výskumný tím Oddelenia teoretickej informatiky

Automaty, formálne jazyky a teória grafov

Výskum: skúmame popisnú a výpočtovú zložitosť automatov a algoritmov,

Ako to robíme: efektívna reprezentácia jazykov pomocou automatov, analýza stavovej zložitosti pre automaty a kombinované jazykové operácie, ako aj návrh časovo efektívnych algoritmov v danej oblasti, vlastnosti a aplikácie Boolovských a alternujúcich automatov, zásobníkové automaty s rôznymi druhmi obmedzení, grafové modely,

Aplikácie do praxe: využitie prekladačov pre rozpoznávanie podtried regulárnych jazykov, bezpečné a efektívne protokoly pre komunikáciu v sieťach

Členovia tímu

Líder: prof. RNDr. Viliam Geffert, DrSc.

  • doc. RNDr. Jozef Jirásek, PhD.
  • RNDr. Juraj Šebej, PhD.
  • Mgr. Alexander Szabari, PhD.
  • Mgr. Dominika Pališinová

Projekty

  1. VEGA 1/0479/12 „Kombinatorické štruktúry a zložitosť algoritmov“, 2012-2014
  2. VEGA 1/0142/15 „Kombinatorické štruktúry a zložitosť algoritmov“, 2015-2017
  3. VEGA 1/0056/18 „Popisná a výpočtová zložitosť automatov a algoritmov“, 2018-2020
  4. APVV-15-0091 „Efektívne algoritmy, automaty a dátové štruktúry“, 2016-2020
  5. VEGA 1/0177/21 „Popisná a výpočtová zložitosť automatov a algoritmov“, 2021-2023

Najnovšie publikácie

  1. Viliam Geffert, Christos A. Kapoutsis, Mohammad Zakzok Complement for two-way alternating automata Acta Informatica 58 (2021) 463–495 čítaj
  2. Viliam Geffert, Zuzana Bednárová Minimal Size of Counters for (Real-Time) Multicounter Automata Fundamenta Informaticae 181 (2021) 99–127 čítaj
  3. Z.Bednárová, V.Geffert, K.Reinhardt, A.Yakaryilmaz: New results on the minimum amount of useful space, International Journal of Foundations of Computer Science, World Scientific, 2016, Vol.27, No.2, pp.259-281 čítaj
  4. V.Geffert, Z.Bednárová, C.Mereghetti, B.Palano: Boolean language operations on nondeterministic automata with a pushdown of constant height, Journal of Computer and System Sciences, Elsevier, 2017, Vol.90, pp.99-114 čítaj
  5. Z.Bednárová, V.Geffert: Two double-exponential gaps for automata with a limited pushdown, Information and Computation, Elsevier, 2017, Vol.253, pt.3, pp.381-398 čítaj
  6. V.Geffert, Z.Bednárová, A.Szabari: Input-driven pushdown automata for edit distance neighborhood, Proc. of DLT 2019 (Developments in Language Theory), Lecture Notes in Computer Science 11647, Springer-Verlag, 2019, pp. 113-126 (Warsaw, Poland, August 5-9, 2019, P.Hofman, M.Skrzypczak – eds.) ISSN 0302-9743, ISBN 978-3-030-24885-7 čítaj
  7. V.Geffert: Unary coded PSPACE-complete languages in ASPACE(loglog n), Theory of Computing Systems, Springer-Verlag, 2019, Vol.63, No.4, pp.688-714 ISSN 1432-4350 čítaj