Operational state complexity of unary NFAs with finite nondeterminism

被引：4

作者：

Palioudakis, Alexandros ^{[1
]}

Salomaa, Kai ^{[2
]}

Akl, Selim G. ^{[2
]}

机构：

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

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

来源：

THEORETICAL COMPUTER SCIENCE | 2016年 / 610卷

关键词：

Finite automata; Limited nondeterminism; State complexity; Language operations; Unary regular languages; Descriptional complexity; DESCRIPTIONAL COMPLEXITY; AUTOMATA;

D O I：

10.1016/j.tcs.2015.07.006

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study the state complexity of language operations for unary NFAs with limited nondeterminism. We consider the Boolean operations, concatenation, and Kleene star. We give upper bounds for the state complexity of these language operations and lower bounds that are fairly close to the upper bounds. Our constructions rely on the fact that minimal unary NFAs with limited nondeterminism can be found in Chrobak normal form for most measures of nondeterminism. The measures of nondeterminism which are considered here with the above property are tree width, advice, and trace. (C) 2015 Elsevier B.V. All rights reserved.

引用

页码：108 / 120

页数：13

共 35 条

[1] An optimal lower bound for the Frobenius problem [J].

Aliev, Iskander M. ;

Gruber, Peter M. .

JOURNAL OF NUMBER THEORY, 2007, 123 (01) :71-79

[2]

[Anonymous], 1909, Handbuch der Lehre von der Verteilung der Primzahlen

[3]

Bach E., 1996, ALGORITHMIC NUMBER T, V1

[4] The Frobenius problem, rational polytopes, and Fourier-Dedekind sums [J].

Beck, M ;

Diaz, R ;

Robins, S .

JOURNAL OF NUMBER THEORY, 2002, 96 (01) :1-21

[5] FINITE AUTOMATA AND UNARY LANGUAGES [J].

CHROBAK, M .

THEORETICAL COMPUTER SCIENCE, 1986, 47 (02) :149-158

[6] The kth prime is greater than k(lnk+lnlnk-1) for k≥2 [J].

Dusart, P .

MATHEMATICS OF COMPUTATION, 1999, 68 (225) :411-415

[7]

Gao Y., 2012, TECHNICAL REPORT

[8]

Gawrychowski P, 2011, LECT NOTES COMPUT SC, V6807, P142, DOI 10.1007/978-3-642-22256-6_14

[9] Magic numbers in the state hierarchy of finite automata [J].

Geffert, Villam .

INFORMATION AND COMPUTATION, 2007, 205 (11) :1652-1670

[10]

Goldstine J, 2002, J UNIVERS COMPUT SCI, V8, P193

← 1 2 3 4 →