Detekcia chýb pomocou susednosti a editačnej vzdialenosti vstupom riadených zásobníkových automatov


Autor: Matúš Piroh
Vedúci práce: RNDr. Zuzana Bednárová, PhD.
Konzultant: Mgr. Alexander Szabari, PhD.

Ciele práce:

  • Preskúmať a popísať model vstupom riadeného zásobníkového automatu a pojem susednosti a editačnej vzdialenosti.
  • Analyzovať a spracovať existujúce konštrukcie vstupom riadených zásobníkových automatov z gramatík v špeciálnych formách.
  • Implementovať túto konštrukciu a použiť ju na detekciu chýb v dokumentoch (napr. XML).
  • Rozšíriť zostrojený algoritmus o hľadanie editačnej vzdialenosti daného vstupu od daného jazyka určeného gramatikou.

Dokončené úlohy

  • Naštudovať literatúru o input-driven automatoch
  • Analyzovať konštrukcie týchto automatov
  • Zostrojiť algoritmus na získanie input-driven automatu z gramatiky
  • Analyzovať a navrhnúť špeciálny tvar gramatiky

Nasledujúce úlohy

  • Vytvorenie jednoduchého editora pre gramatiky
  • Implementácia algoritmu na získanie input-driven automatu
  • Simulácia tohto programu na dokumentoch (napr. XML)
  • Rozširenie programu o hľadanie chýb (editačnej vzdialenosti)

Zdroje:

  • A. Okhotin, K. Salomaa: Edit Distance Neighbourhoods of Input-Driven Pushdown Automata. In: CSR 2017, LNCS 10304, pp. 260-272 (2017)
  • R. Alur, P. Madhusudan: Visibly pushdown languages. In: ACM Symposium on Theory od Computing, STOC 2004, Chicago, USA 13-16 June 2004, pp. 202-211 (2004)
  • J. E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to automata theory, languages, and computation - international edition (2. ed). Addison-Wesley (2003)