State complexity of basic language operations combined with reversal

被引：25

作者：

Liu, Guangwu ^{[1
,2
]}

Martin-Vide, Carlos ^{[2
]}

Salomaa, Arto ^{[3
]}

Yu, Sheng ^{[4
]}

机构：

[1] Wuhan Univ Technol, Sch Transportat, Wuhan 430063, Peoples R China

[2] Univ Rovira & Virgili, Res Grp Math Linguist, Tarragona 43005, Spain

[3] Turku Ctr Comp Sci, Turku 20520, Finland

[4] Univ Western Ontario, Dept Comp Sci, London, ON N6A 5B7, Canada

来源：

INFORMATION AND COMPUTATION | 2008年 / 206卷 / 9-10期

基金：

中国国家自然科学基金; 加拿大自然科学与工程研究理事会;

关键词：

finite state automata; regular languages; state complexity; combined operations;

D O I：

10.1016/j.ic.2008.03.018

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study the state complexity of combined operations on regular languages. Each of the combined operations is a basic operation combined with reversal. We show that their state complexities are all very different from the compositions of state complexities of individual operations. Crown copyright (C) 2008 Published by Elsevier Inc. All rights reserved.

引用

页码：1178 / 1186

页数：9

共 15 条

[1]

GAO Y, DESCRIPTIONAL COMPLE, P153

[2] MULTIPLE-ENTRY FINITE AUTOMATA [J].

GILL, A ;

KOU, LT .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1974, 9 (01) :1-19

[3]

Harel D., 1998, MODELING REACTIVE SY

[4]

HOPCROFT JE, 2007, 825 TUCS

[5]

JEFFREY EF, 1997, MASTERING REGULAR EX

[6]

Karttunen L, 2001, LECT NOTES COMPUT SC, V2088, P34

[7]

Linz Peter., 2006, INTRO FORMAL LANGUAG, V4th

[8]

LUCIAN I, 2003, P 2003 INT C PAR DIS, P1706

[9] On the state complexity of reversals of regular languages [J].

Salomaa, A ;

Wood, D ;

Yu, S .

THEORETICAL COMPUTER SCIENCE, 2004, 320 (2-3) :315-329

[10]

Salomaa A., 1969, THEORY AUTOMATA

← 1 2 →