Nondeterministic state complexity of nested word automata

被引：20

作者：

Han, Yo-Sub ^{[2
]}

Salomaa, Kai ^{[1
]}

机构：

[1] Queens Univ, Sch Comp, Kingston, ON K7L 3N6, Canada

[2] Yonsei Univ, Dept Comp Sci, Seoul 120749, South Korea

来源：

THEORETICAL COMPUTER SCIENCE | 2009年 / 410卷 / 30-32期

基金：

加拿大自然科学与工程研究理事会;

关键词：

State complexity; Nondeterminism; Finite automata on nested words; Language operations; REGULAR LANGUAGES; FINITE AUTOMATA; TRANSITION COMPLEXITY;

D O I：

10.1016/j.tcs.2009.01.004

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study the nondeterministic state complexity of Boolean operations oil regular languages of nested words. For union and intersection we obtain matching upper and lower bounds. For complementation of a nondeterministic nested word automaton with n states we establish a lower bound Omega(root n!) that is significantly worse than the exponential lower bound for ordinary nondeterministic finite automata (NFA). We develop techniques to prove lower bounds for the size of nondeterministic nested word automata that extend the known techniques used for NFAs. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：2961 / 2971

页数：11

共 18 条

[1] Alur R, 2005, LECT NOTES COMPUT SC, V3580, P1102
[2] ALUR R, ADDING NESTING STRUC
[3] Alur R, 2006, LECT NOTES COMPUT SC, V4036, P1
[4] Arenas M, 2007, LECT NOTES COMPUT SC, V4596, P888
[5] INTERSECTION AND UNION OF REGULAR LANGUAGES AND STATE COMPLEXITY
BIRGET, JC
[J]. INFORMATION PROCESSING LETTERS, 1992, 43 (04) : 185 - 190
[6] Lower bounds for the transition complexity of NFAs
Domaratzki, Michael
Salomaa, Kai
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2008, 74 (07) : 1116 - 1130
[7] A lower bound technique for the size of nondeterministic finite automata
Glaister, I
Shallit, J
[J]. INFORMATION PROCESSING LETTERS, 1996, 59 (02) : 75 - 77
[8] Gruber H, 2007, LECT NOTES COMPUT SC, V4588, P205
[9] Holzer M., 2003, International Journal of Foundations of Computer Science, V14, P1087, DOI 10.1142/S0129054103002199
[10] Communication complexity method for measuring nondeterminism in finite automata
Hromkovic, J
Seibert, S
Karhumäki, J
Klauck, H
Schnitger, G
[J]. INFORMATION AND COMPUTATION, 2002, 172 (02) : 202 - 217

← 1 2 →