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 条
  • [21] LANGUAGES RECOGNIZED BY NONDETERMINISTIC QUANTUM FINITE AUTOMATA
    Yakaryilmaz, Abuzer
    Say, A. C. Cem
    QUANTUM INFORMATION & COMPUTATION, 2010, 10 (9-10) : 747 - 770
  • [22] Converting finite width AFAs to nondeterministic and universal finite automata
    Zakzok, Mohammad
    Salomaa, Kai
    THEORETICAL COMPUTER SCIENCE, 2024, 996
  • [23] A Novel Stream Cipher Based on Nondeterministic Finite Automata
    Khaleel, Ghassan
    Turaev, Sherzod
    Zhukabayeva, Tamara
    PROCEEDINGS OF THE 2016 CONFERENCE ON INFORMATION TECHNOLOGIES IN SCIENCE, MANAGEMENT, SOCIAL SPHERE AND MEDICINE (ITSMSSM), 2016, 51 : 110 - 115
  • [24] Robust models to infer flexible nondeterministic finite automata
    Jastrzab, Tomasz
    Lardeux, Frederic
    Monfroy, Eric
    JOURNAL OF COMPUTATIONAL SCIENCE, 2024, 79
  • [25] A lower bound technique for the size of nondeterministic finite automata
    Glaister, I
    Shallit, J
    INFORMATION PROCESSING LETTERS, 1996, 59 (02) : 75 - 77
  • [26] A Supervisor Synthesis Tool for Finite Nondeterministic Automata with Data
    Kirilov, Aleksandar
    Martinovikj, Darko
    Mishevski, Kristijan
    Petkovska, Marija
    Trajcheska, Zlatka
    Markovski, Jasen
    SOFTWARE ENGINEERING AND FORMAL METHODS, 2014, 8368 : 101 - 112
  • [27] FINITE AUTOMATA HAVING COST FUNCTIONS - NONDETERMINISTIC MODELS
    IBARAKI, T
    INFORMATION AND CONTROL, 1978, 37 (01): : 40 - 69
  • [28] On input-revolving deterministic and nondeterministic finite automata
    Bensch, Suna
    Bordihn, Henning
    Holzer, Markus
    Kutrib, Martin
    INFORMATION AND COMPUTATION, 2009, 207 (11) : 1140 - 1155
  • [29] Some algorithms for equivalent transformation of nondeterministic finite automata
    B. F. Mel’nikov
    M. R. Saifullina
    Russian Mathematics, 2009, 53 (4) : 54 - 57
  • [30] Efficient POSIX submatch extraction on nondeterministic finite automata
    Borsotti, Angelo
    Trofimovich, Ulya
    SOFTWARE-PRACTICE & EXPERIENCE, 2021, 51 (02): : 159 - 192
12345