On the state complexity of closures and interiors of regular languages with subwords and superwords

被引：9

作者：

Karandikar, P. ^{[1
,3
]}

Niewerth, M. ^{[2
]}

Schnoebelen, Ph. ^{[3
]}

机构：

[1] Chennai Math Inst, Chennai, Tamil Nadu, India

[2] Univ Bayreuth, Bayreuth, Germany

[3] CNRS, LSV, ENS Cachan, F-75700 Paris, France

来源：

THEORETICAL COMPUTER SCIENCE | 2016年 / 610卷

关键词：

Finite automata and regular languages; Subwords and superwords; State complexity; Combined operations; Closures and interiors of regular languages; SIZE; SETS;

D O I：

10.1016/j.tcs.2015.09.028

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The downward and upward closures of a regular language L are obtained by collecting all the subwords and superwords of its elements, respectively. The downward and upward interiors of L are obtained dually by collecting words having all their subwords and superwords in L, respectively. We provide lower and upper bounds on the size of the smallest automata recognizing these closures and interiors. We also consider the computational complexity of decision problems for closures of regular languages. (C) 2015 Elsevier B.V. All rights reserved.

引用

页码：91 / 107

页数：17

共 47 条

[1] Using forward reachability analysis for verification of lossy channel systems [J].

Abdulla, PA ;

Collomb-Annichini, A ;

Bouajjani, A ;

Jonsson, B .

FORMAL METHODS IN SYSTEM DESIGN, 2004, 25 (01) :39-65

[2]

[Anonymous], 1976, P 17 ANN S FDN COMPU

[3]

[Anonymous], 2008, Texts in Logic and Games

[4]

Arfi M., 1987, LNCS, V247, P198

[5]

Bachmeier Georg, 2015, Language and Automata Theory and Applications. 9th International Conference, LATA 2015. Proceedings: LNCS 8977, P473, DOI 10.1007/978-3-319-15579-1_37

[6] SEARCHING SUBSEQUENCES [J].

BAEZAYATES, RA .

THEORETICAL COMPUTER SCIENCE, 1991, 78 (02) :363-376

[7] Computable fixpoints in well-structured symbolic model checking [J].

Bertrand, N. ;

Schnoebelen, P. .

FORMAL METHODS IN SYSTEM DESIGN, 2013, 43 (02) :233-267

[8]

Bianchi MP, 2012, LECT NOTES COMPUT SC, V7386, P89, DOI 10.1007/978-3-642-31623-4_7

[9] The state complexity of Sigma*(L)over-bar and its connection with temporal logic [J].

Birget, JC .

INFORMATION PROCESSING LETTERS, 1996, 58 (04) :185-188

[10] PARTIAL ORDERS ON WORDS, MINIMAL ELEMENTS OF REGULAR LANGUAGES, AND STATE COMPLEXITY [J].

BIRGET, JC .

THEORETICAL COMPUTER SCIENCE, 1993, 119 (02) :267-291

← 1 2 3 4 5 →