State complexity of some operations on binary regular languages

被引：92

作者：

Jirásková, G ^{[1
]}

机构：

[1] Slovak Acad Sci, Math Inst, Kosice 04001, Slovakia

来源：

THEORETICAL COMPUTER SCIENCE | 2005年 / 330卷 / 02期

关键词：

state complexity; regular language operations; binary languages;

D O I：

10.1016/j.tcs.2004.04.011

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We investigate the state complexity of some operations on binary regular languages. In particular, we consider the concatenation of languages represented by deterministic finite automata, and the reversal and complementation of languages represented by nondeterministic finite automata. We prove that the upper bounds on the state complexity of these operations, which were known to be tight for larger alphabets, are tight also for binary alphabets. (C) 2004 Elsevier B.V. All rights reserved.

引用

页码：287 / 298

页数：12

共 31 条

[1] BERMAN P, 1977, 304 POL AC SCI
[2] PARTIAL ORDERS ON WORDS, MINIMAL ELEMENTS OF REGULAR LANGUAGES, AND STATE COMPLEXITY
BIRGET, JC
[J]. THEORETICAL COMPUTER SCIENCE, 1993, 119 (02) : 267 - 291
[3] INTERSECTION AND UNION OF REGULAR LANGUAGES AND STATE COMPLEXITY
BIRGET, JC
[J]. INFORMATION PROCESSING LETTERS, 1992, 43 (04) : 185 - 190
[4] BIRGET JC, 2002, ERRATUM PARTIAL ORDE
[5] Campeanu C., 2002, Journal of Automata, Languages and Combinatorics, V7, P303
[6] CAMPEANU C, 2001, P 4 INT WORKSH IMPL, V2214, P60
[7] Domaratzki M., 2002, Journal of Automata, Languages and Combinatorics, V7, P455
[8] ELLUL K, 2002, THESIS U WATERLOO
[9] A lower bound technique for the size of nondeterministic finite automata
Glaister, I
Shallit, J
[J]. INFORMATION PROCESSING LETTERS, 1996, 59 (02) : 75 - 77
[10] Holzer M., 2001, Journal of Automata, Languages and Combinatorics, V6, P453

← 1 2 3 4 →