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 条
  • [31] Deterministic Formal Modeling of Smart Lightening System using Internet of Things
    Latif, Saba
    Afzaal, Hamra
    Rehman, Aniqa
    Zafar, Nazir Ahmad
    [J]. 2018 12TH INTERNATIONAL CONFERENCE ON MATHEMATICS, ACTUARIAL SCIENCE, COMPUTER SCIENCE AND STATISTICS (MACS), 2018,
  • [32] Freeze After Writing Quasi-Deterministic Parallel Programming with LVars
    Kuper, Lindsey
    Turon, Aaron
    Krishnaswami, Neelakantan R.
    Newton, Ryan R.
    [J]. ACM SIGPLAN NOTICES, 2014, 49 (01) : 257 - 270
  • [33] Modeling Dynamic Single-Cell and Coupling Faults via Automata Models
    Hayrapetyan, Davit
    Manukyan, Aleksandr
    [J]. 2017 ELEVENTH INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE AND INFORMATION TECHNOLOGIES (CSIT), 2017, : 65 - 68
  • [34] A Novel Deterministic Threshold Proxy Re-Encryption Scheme From Lattices
    Hua, Na
    Li, Juyan
    Zhang, Kejia
    Zhang, Long
    [J]. INTERNATIONAL JOURNAL OF INFORMATION SECURITY AND PRIVACY, 2022, 16 (01)
  • [35] An Overview of the Deterministic Dynamic Associative Memory (DDAM) Model for Case Representation and Retrieval
    Pantazi, Stefan
    [J]. CASE-BASED REASONING RESEARCH AND DEVELOPMENT, PROCEEDINGS, 2009, 5650 : 256 - 269
  • [36] Lattices in finite fields
    Hamahata Y.
    [J]. Beiträge zur Algebra und Geometrie / Contributions to Algebra and Geometry, 2015, 56 (1): : 313 - 324
  • [37] Finite Dedekind sums
    Hamahata, Yoshinori
    [J]. ARITHMETIC OF FINITE FIELDS, PROCEEDINGS, 2008, 5130 : 11 - 18
  • [38] WEIL REPRESENTATIONS OF FINITE GENERAL LINEAR GROUPS AND FINITE SPECIAL LINEAR GROUPS
    Tiep, Pham Huu
    [J]. PACIFIC JOURNAL OF MATHEMATICS, 2015, 279 (1-2) : 481 - 498
  • [39] Measurement of surface plasmon correlation length differences using Fibonacci deterministic hole arrays
    Tho Duc Nguyen
    Nahata, Ajay
    Vardeny, Z. Valy
    [J]. OPTICS EXPRESS, 2012, 20 (14): : 15222 - 15231
  • [40] An axiomatic approach to finite means
    Campion, Maria J.
    Candeal, Juan C.
    Catalan, Raquel G.
    Giarlotta, Alfio
    Greco, Salvatore
    Indurain, Esteban
    Montero, Javier
    [J]. INFORMATION SCIENCES, 2018, 457 : 12 - 28
12345