Extended Nondeterministic Finite Automata

被引：4
|
作者：
Melnikov, Boris [1 ]
机构：
[1] Togliatti State Univ, Fac Math & Informat, Tolyatti 445667, Russia
来源：
FUNDAMENTA INFORMATICAE | 2010年 / 104卷 / 03期
关键词：
Nondeterministic finite automata; extended automata; basic automaton; algorithms of simplification;
D O I：
10.3233/FI-2010-348
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
We consider a new expansion of nondeterministic finite automata. The goals of this consideration are: to apply some algorithms of such expansion for various problems of minimization of classical nondeterministic automata; to use such automata for describing practical anytime algorithms for the same problems of minimization; using such automata, we often can simplify some proofs for algorithms of simplification of usual nondeterministic automata.
引用
收藏
页码：255 / 265
页数：11
相关论文
共 50 条
  • [41] Regularly extended two-way nondeterministic tree automata
    Brüggemann-Klein, A
    Wood, D
    IMPLEMENTATION AND APPLICATION OF AUTOMATA, 2001, 2088 : 57 - 66
  • [42] Algorithmic Formal Proof of Equivalence of Nondeterministic and Deterministic Finite Automata
    Zafar, Nazir Ahmad
    Shah, Syed Hasnain Haider
    ICECT: 2009 INTERNATIONAL CONFERENCE ON ELECTRONIC COMPUTER TECHNOLOGY, PROCEEDINGS, 2009, : 108 - +
  • [43] Nondeterministic finite automata - Recent results on the descriptional and computational complexity
    Holzer, Markus
    Kutrib, Martin
    IMPLEMENTATION AND APPLICATION OF AUTOMATA, PROCEEDINGS, 2008, 5148 : 1 - +
  • [44] Analogs of Fagin's Theorem for Small Nondeterministic Finite Automata
    Kapoutsis, Christos A.
    Lefebvre, Nans
    DEVELOPMENTS IN LANGUAGE THEORY (DLT 2012), 2012, 7410 : 202 - 213
  • [45] A new algorithm of the state-minimization for the nondeterministic finite automata
    B. F. Melnikov
    Korean Journal of Computational & Applied Mathematics, 1999, 6 (2): : 277 - 290
  • [46] Note on the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata
    Mereghetti, C
    Palano, B
    Pighizzini, G
    RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS, 2001, 35 (05): : 477 - 490
  • [47] Lower Bound Methods for the Size of Nondeterministic Finite Automata Revisited
    Tamm, Hellis
    van der Merwe, Brink
    LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS (LATA 2017), 2017, 10168 : 261 - 272
  • [48] NONDETERMINISTIC FINITE AUTOMATA - RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
    Holzer, Markus
    Kutrib, Martin
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2009, 20 (04) : 563 - 580
  • [49] Translating regular expressions into small ε-free nondeterministic finite automata
    Hromkovic, J
    Seibert, S
    Wilke, T
    STACS 97 - 14TH ANNUAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, 1997, 1200 : 55 - 66
  • [50] Translating regular expressions into small ε-free nondeterministic finite automata
    Hromkovic, J
    Seibert, S
    Wilke, T
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2001, 62 (04) : 565 - 588
12345