Detail publikace

Automata Size Reduction by Procedure Finding

ŠEDÝ Michal a HOLÍK Lukáš. Automata Size Reduction by Procedure Finding. In: Proceedings of NFM'25. Lecture Notes in Computer Science. Williamsburg: Springer Nature Switzerland AG, 2025, s. 421-440. ISSN 0302-9743. Dostupné z: https://link.springer.com/content/pdf/10.1007/978-3-031-93706-4_24.pdf?pdf=inline%20link
Název česky
Redukce velikosti automatů vyhledáváním procedur
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Šedý Michal, Ing. (UITS FIT VUT)
Holík Lukáš, doc. Mgr., Ph.D. (UITS FIT VUT)
URL
Klíčová slova

Nedeterministické konečné automaty, Redukce, Regulární výrazy, Systém detekce průniku v sítích

Abstrakt

Představujeme nový přístup ke zmenšování velikosti konečných automatů prostřednictvím komprese opakujících se podgrafů. Tyto opakující se podgrafy lze chápat jako volání jedné společné procedury. Místo toho, aby bylo každé takové volání reprezentováno explicitně, může být nahrazeno jedinou procedurou, která využívá malou paměť pro uchování kontextu volání. Ilustrujeme základní technické detaily implementace této myšlenky, kde procedura využívá jednoduchý registr o konečném možném množství hodnot jako paměť. Navrhujeme metody pro identifikaci opakujících se podgrafů, jejich sloučení do procedur a měření výsledného zmenšení velikosti automatu. Už tato základní implementace redukce pomocí vyhledávání procedur přináší prakticky významné výsledky, zejména v oblasti akcelerovaného pattern matchingu na FPGA, kde je velikost automatu hlavním úskalím. Dosahujeme zmenšení až o 70 % u automatů, které již byly minimalizovány pomocí pokročilých stávajících metod.

Rok
2025
Strany
421-440
Časopis
Lecture Notes in Computer Science, č. 15682, ISSN 0302-9743
Sborník
Proceedings of NFM'25
Řada
Lecture Notes in Computer Science
Konference
NASA Formal Methods Symposium 2025, Williamsburg, US
Vydavatel
Springer Nature Switzerland AG
Místo
Williamsburg, US
DOI
10.1007/978-3-031-93706-4_24
BibTeX 
@INPROCEEDINGS{FITPUB13501,
   author = "Michal \v{S}ed\'{y} and Luk\'{a}\v{s} Hol\'{i}k",
   title = "Automata Size Reduction by Procedure Finding",
   pages = "421--440",
   booktitle = "Proceedings of NFM'25",
   series = "Lecture Notes in Computer Science",
   journal = "Lecture Notes in Computer Science",
   number = 15682,
   year = 2025,
   location = "Williamsburg, US",
   publisher = "Springer Nature Switzerland AG",
   ISSN = "0302-9743",
   doi = "10.1007/978-3-031-93706-4\_24",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/13501"
}
Nahoru