A Tree Automata Library
Felix Frýbort · Brno University of Technology Digital Library (Brno University of Technology) · 2026
Stromové automaty se používají ve formální verifikaci, analýze programů a zpracování dat se stromovou strukturou. Existující knihovny pro práci se stromovými automaty buď vyžadují determinizaci, postrádají potřebné optimalizace, nebo již nejsou aktivně vyvíjeny a udržovány. Tato práce představuje návrh a implementaci knihovny pro práci se stromovými automaty, vytvořenou jako rozšíření knihovny Mata, která slouží k práci s konečnými automaty. Výsledkem je knihovna, která upřednostňuje nedeterministické reprezentace, umožňuje přístup k nízkoúrovňovým strukturám a je kompatibilní se stávající infrastrukturou. Jsou implementovány a vyhodnoceny standardní operace, jako je sjednocení, průnik, determinizace, komplement a inkluze. Experimentální výsledky ukazují, že implementovaná knihovna dosahuje výkonu srovnatelného s knihovnou VATA, nejrelevantnější existující knihovnou pro stromové automaty.