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 条
[41]   Dedekind sums in finite characteristic [J].
Hamahata, Yoshinori .
PROCEEDINGS OF THE JAPAN ACADEMY SERIES A-MATHEMATICAL SCIENCES, 2008, 84 (07) :89-92
[42]   Finite Distributive Concept Algebras [J].
Bernhard Ganter ;
Léonard Kwuida .
Order, 2006, 23 :235-248
[43]   The ordering of idempotents in a finite ring [J].
Dolzan, David .
PUBLICATIONES MATHEMATICAE-DEBRECEN, 2016, 89 (1-2) :97-104
[44]   Solitary quotients of finite groups [J].
Tarnauceanu, Marius .
CENTRAL EUROPEAN JOURNAL OF MATHEMATICS, 2012, 10 (02) :740-747
[45]   Finite quadratic modules and lattices [J].
Zhu, Xiao-Jie .
COMMUNICATIONS IN ALGEBRA, 2023, :604-629
[46]   Finite representation of commutator sequences [J].
Aichinger, Erhard ;
Mudrinski, Nebojsa .
INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 2022, 32 (08) :1513-1543
[47]   Finite distributive concept algebras [J].
Ganter, Bernhard ;
Kwuida, Leonard .
ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2006, 23 (2-3) :235-248
[48]   The Birkhoff Completion of Finite Lattices [J].
Abdulla, Mohammad ;
Hirth, Johannes ;
Stumme, Gerd .
CONCEPTUAL KNOWLEDGE STRUCTURES, CONCEPTS 2024, 2024, 14914 :20-35
[49]   Finite convex geometries of circles [J].
Czedli, Gabor .
DISCRETE MATHEMATICS, 2014, 330 :61-75
[50]   Finite Semilattices with Many Congruences [J].
Czedli, Gabor .
ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2019, 36 (02) :233-247
12345