Detail publikace

When Simulation Meets Antichains (On Checking Language Inclusion of Nondeterministic Finite (Tree) Automata)

HOLÍK, L.; VOJNAR, T.; ABDULLA, P.; CHEN, Y.; MAYR, R. When Simulation Meets Antichains (On Checking Language Inclusion of Nondeterministic Finite (Tree) Automata). FIT-TR-2010-01, Brno: Faculty of Information Technology BUT, 2010. p. 0-0.
Název česky
Když se simulace potká s protiřetězcem (za testováním jazykové inkluze nedeterministických konečných (stromových) automatů)
Typ
zpráva odborná
Jazyk
anglicky
Autoři
Holík Lukáš, doc. Mgr., Ph.D. (UITS)
Vojnar Tomáš, prof. Ing., Ph.D. (UITS)
Abdulla Parosh
Chen Yu-Fang
Mayr Richard
URL
Klíčová slova

finite automata, tree automata, language inclusion, universality, simulation, antichain

Abstrakt

Navrhli jsme efektivní metody pro testování universality a jazykové inkluze nedterminisitckých (stromových) automatů. Hlavní myšlěnkou je zde využití relací simulace na stavech automatu v rámci takzvaných "protiřetězcových algoritmů". Efektivitu nových algoritmů jsme experimentálně ověřili.

Rok
2010
Strany
22
Vydavatel
Faculty of Information Technology BUT
Místo
FIT-TR-2010-01, Brno
BibTeX 
@techreport{BUT192702,
  author="Lukáš {Holík} and Tomáš {Vojnar} and Parosh {Abdulla} and Yu-Fang {Chen} and Richard {Mayr}",
  title="When Simulation Meets Antichains (On Checking Language Inclusion of Nondeterministic Finite (Tree) Automata)",
  year="2010",
  publisher="Faculty of Information Technology BUT",
  address="FIT-TR-2010-01, Brno",
  pages="22",
  url="http://www.fit.vutbr.cz/~holik/pub/FIT-TR-2010-001.pdf"
}
Nahoru