Subset construction complexity for homogeneous automata, position automata and ZPC-structures

被引：12
作者：
Champarnaud, JM [1 ]
机构：
[1] Univ Rouen, LIFAR, F-76821 Mont St Aignan, France
来源：
THEORETICAL COMPUTER SCIENCE | 2001年 / 267卷 / 1-2期
关键词：
subset construction; homogeneous automaton; position sets; position automaton; ZPC-structure;
D O I：
10.1016/S0304-3975(00)00293-0
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
The aim of this paper is to investigate how subset construction performs on specific families of automata. A new upper bound on the number of states of the subset-automaton is established in the case of homogeneous automata. The complexity of the two basic steps of subset construction, i.e. the computation of deterministic transitions and the set equality tests, is examined depending on whether the nondeterministic automaton is an unrestricted one, an homogeneous one. a position one or a ZPC-structure, which is an implicit construction for a position automaton. (C) 2001 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：17 / 34
页数：18
相关论文
共 20 条
  • [1] Aho A.V., 1974, The Design and Analysis of Computer Algorithms
  • [2] [Anonymous], ANN MATH STUD
  • [3] Partial derivatives of regular expressions and finite automaton constructions
    Antimirov, V
    [J]. THEORETICAL COMPUTER SCIENCE, 1996, 155 (02) : 291 - 319
  • [4] AUTOMATE, A COMPUTING PACKAGE FOR AUTOMATA AND FINITE-SEMIGROUPS
    CHAMPARNAUD, JM
    HANSEL, G
    [J]. JOURNAL OF SYMBOLIC COMPUTATION, 1991, 12 (02) : 197 - 220
  • [5] Glushkov V M, 1961, Russian Mathematical Survey, V16, P1, DOI DOI 10.1070/RM1961V016N05ABEH004112
  • [6] Hopcroft J. E., 2007, Introduction to Automata Theory, Languages and Computation
  • [7] Johnson JH, 1997, LECT NOTES COMPUT SC, V1260, P64
  • [8] JOHNSON JH, 1986, UNPUB PROGRAM COMPUT
  • [9] LESLIE TKS, 1996, UNPUB EXPECTED PERFO
  • [10] LESLIE TKS, 1992, CS9229 U WAT DEP COM
12