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 条
  • [21] A Deterministic Reduction for the Gap Minimum Distance Problem
    Cheng, Qi
    Wan, Daqing
    STOC'09: PROCEEDINGS OF THE 2009 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2009, : 33 - 38
  • [22] Lower Bounds for Synchronizing Word Lengths in Partial Automata
    De Bondt, Michiel
    Don, Henk
    Zantema, Hans
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2019, 30 (01) : 29 - 60
  • [23] Additivity Principle in High-Dimensional Deterministic Systems
    Saito, Keiji
    Dhar, Abhishek
    PHYSICAL REVIEW LETTERS, 2011, 107 (25)
  • [24] The complexity of computing the behaviour of lattice automata on infinite trees
    Lehmann, Karsten
    Penaloza, Rafael
    THEORETICAL COMPUTER SCIENCE, 2014, 534 : 53 - 68
  • [25] Tighter Reductions for Deterministic Identity-Based Signatures
    Yanai, Naoto
    Fujiwara, Toru
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2018, E101A (01): : 64 - 76
  • [26] Automata Based Railway Gate Control System at Level Crossing
    Rehman, Aniqa
    Latif, Saba
    Zafar, Nazir Ahmad
    2019 INTERNATIONAL CONFERENCE ON COMMUNICATION TECHNOLOGIES (COMTECH), 2019, : 30 - 35
  • [27] Effective target arrangement in a deterministic scale-free graph
    Agliari, E.
    Burioni, R.
    Manzotti, A.
    PHYSICAL REVIEW E, 2010, 82 (01):
  • [28] Steering Multiple Reverse Current into Unidirectional Current in Deterministic Ratchets
    Wei Du-Qu
    Luo Xiao-Shu
    Qin Ying-Hua
    COMMUNICATIONS IN THEORETICAL PHYSICS, 2011, 56 (05) : 891 - 894
  • [29] An automata approach to match gapped sequence tags against protein database
    Han, Y
    Ma, B
    Zhang, KZ
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2005, 16 (03) : 487 - 497
  • [30] Ranks of fuzzy matrices. Applications in state reduction of fuzzy automata
    Stamenkovic, Aleksandar
    Ciric, Miroslav
    Basic, Milan
    FUZZY SETS AND SYSTEMS, 2018, 333 : 124 - 139
12345