Detail publikace

Automata Size Reduction by Procedure Finding

ŠEDÝ, M.; HOLÍK, L. Automata Size Reduction by Procedure Finding. Proceedings of NFM'25. Lecture Notes in Computer Science. Lecture Notes in Computer Science. Williamsburg: Springer Nature Switzerland AG, 2025. p. 421-440. ISSN: 0302-9743.
Název česky
Redukce velikosti automatů vyhledáváním procedur
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Šedý Michal, Ing. (UITS)
Holík Lukáš, doc. Mgr., Ph.D. (UITS)
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
DOI
10.1007/978-3-031-93706-4_24
BibTeX 
@inproceedings{BUT197713,
  author="Michal {Šedý} and Lukáš {Holík}",
  title="Automata Size Reduction by Procedure Finding",
  booktitle="Proceedings of NFM'25",
  year="2025",
  series="Lecture Notes in Computer Science",
  journal="Lecture Notes in Computer Science",
  number="15682",
  pages="421--440",
  publisher="Springer Nature Switzerland AG",
  address="Williamsburg",
  doi="10.1007/978-3-031-93706-4\{_}24",
  issn="0302-9743",
  url="https://link.springer.com/content/pdf/10.1007/978-3-031-93706-4_24.pdf?pdf=inline%20link"
}
Nahoru