Failure Deterministic Finite Automata

被引：0

作者：

Kourie, Derrick G. ^{[1
]}

Watson, Bruce W. ^{[2
]}

Cleophas, Loek ^{[1
,3
]}

Venter, Fritz ^{[1
]}

机构：

[1] Univ Pretoria, ZA-0002 Pretoria, South Africa

[2] Univ Stellenbosch, ZA-7600 Stellenbosch, South Africa

[3] Eindhoven Univ Technol, NL-5600 MB Eindhoven, Netherlands

来源：

PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2012 | 2012年

关键词：

failure arcs; DFA; formal concept analysis; LATTICES;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Inspired by failure functions found in classical pattern matching algorithms, a failure deterministic finite automaton (FDFA) is defined as a formalism to recognise a regular language. An algorithm, based on formal concept analysis, is proposed for deriving from a given deterministic finite automaton (DFA) a language-equivalent FDFA. The FDFA's transition diagram has fewer arcs than that of the DFA. A small modification to the classical DFA's algorithm for recognising language elements yields a corresponding algorithm for an FDFA.

引用

页码：28 / 41

页数：14

共 50 条

[1] On Bidirectional Deterministic Finite Automata
Dieck, Simon
Verwer, Sicco
IMPLEMENTATION AND APPLICATION OF AUTOMATA, CIAA 2024, 2024, 15015 : 109 - 123
[2] Enumeration of Cryptarithms Using Deterministic Finite Automata
Nozaki, Yuki
Hendrian, Diptarama
Yoshinaka, Ryo
Shinohara, Ayumi
IMPLEMENTATION AND APPLICATION OF AUTOMATA, CIAA 2018, 2018, 10977 : 286 - 298
[3] Incremental construction of minimal deterministic finite cover automata
Campeanu, Cezar
Paun, Andrei
Smith, Jason R.
THEORETICAL COMPUTER SCIENCE, 2006, 363 (02) : 135 - 148
[4] Learning Deterministic Finite Automata Decompositions from Examples and Demonstrations
Lauffer, Niklas
Yalcinkaya, Beyazit
Vazquez-Chanlatte, Marcell
Shah, Ameesh
Seshia, Sanjit A.
2022 FORMAL METHODS IN COMPUTER-AIDED DESIGN, FMCAD, 2022, 3 : 325 - 330
[5] Space-Time Tradeoff in Regular Expression Matching with Semi-Deterministic Finite Automata
Yang, Yi-Hua E.
Prasanna, Viktor K.
2011 PROCEEDINGS IEEE INFOCOM, 2011, : 1853 - 1861
[6] SI-DFA: Sub-expression Integrated Deterministic Finite Automata for Deep Packet Inspection
Khalid, Ayesha
Sen, Rajat
Chattopadhyay, Anupam
2013 IEEE 14TH INTERNATIONAL CONFERENCE ON HIGH PERFORMANCE SWITCHING AND ROUTING (HPSR), 2013, : 164 - 170
[7] A robust QRS complex detection using regular grammar and deterministic automata
Hamdi, Salah
Ben Abdallah, Asma
Bedoui, Mohamed Hedi
BIOMEDICAL SIGNAL PROCESSING AND CONTROL, 2018, 40 : 263 - 274
[8] The verification of conversion algorithms between finite automata
Dongchen JIANG
Wei LI
Science China(Information Sciences), 2018, 61 (02) : 243 - 256
[9] Parallel processing of minimization algorithm for determination Finite Automata
Sun, Yu-Qiang
Lu, Hai-Lian
Li, Yu-Ping
Wang, Hai-Yan
ADVANCED INTELLIGENT COMPUTING THEORIES AND APPLICATIONS: WITH ASPECTS OF CONTEMPORARY INTELLIGENT COMPUTING TECHNIQUES, 2007, 2 : 73 - +
[10] A Predict Deterministic Finite Automaton for Practical Deep Packet Inspection
Wei, Qiang
Li, Yunzhao
Chu, Yanjie
2012 INTERNATIONAL WORKSHOP ON INFORMATION AND ELECTRONICS ENGINEERING, 2012, 29 : 2156 - 2161

← 1 2 3 4 5 →