Expressive capacity of subregular expressions
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 52 (2018) no. 2-3-4, pp. 201-218.

Different types of subregular expressions are studied. Each type is obtained by either omitting one of the regular operations or replacing it by complementation or intersection. For uniformity and in order to allow non-trivial languages to be expressed, the set of literals is a finite set of words instead of letters. The power and limitations as well as relations with each other are considered, which is often done in terms of unary languages. Characterizations of some of the language families are obtained. A finite hierarchy is shown that reveals that the operation complementation is generally stronger than intersection. Furthermore, we investigate the closures of language families described by regular expressions with omitted operation under that operation. While it is known that in case of union this closure captures all regular languages, for the cases of concatenation and star incomparability results are obtained with the corresponding language families where the operation is replaced by complementation.

Reçu le :
DOI : 10.1051/ita/2018014
Classification : 68Q45, 68Q15
Mots clés : Regular expressions, concatenation-free languages, star-free languages, union-free languages, expressive capacity, characterizations, closure properties, subregular hierarchy
Kutrib, Martin 1 ; Wendlandt, Matthias 1

1
@article{ITA_2018__52_2-3-4_201_0,
     author = {Kutrib, Martin and Wendlandt, Matthias},
     editor = {Bordihn, Henning and Nagy, Benedek and Vaszil, Gy\"orgy},
     title = {Expressive capacity of subregular expressions},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {201--218},
     publisher = {EDP-Sciences},
     volume = {52},
     number = {2-3-4},
     year = {2018},
     doi = {10.1051/ita/2018014},
     mrnumber = {3915309},
     zbl = {1475.68162},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2018014/}
}
TY  - JOUR
AU  - Kutrib, Martin
AU  - Wendlandt, Matthias
ED  - Bordihn, Henning
ED  - Nagy, Benedek
ED  - Vaszil, György
TI  - Expressive capacity of subregular expressions
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2018
SP  - 201
EP  - 218
VL  - 52
IS  - 2-3-4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2018014/
DO  - 10.1051/ita/2018014
LA  - en
ID  - ITA_2018__52_2-3-4_201_0
ER  - 
%0 Journal Article
%A Kutrib, Martin
%A Wendlandt, Matthias
%E Bordihn, Henning
%E Nagy, Benedek
%E Vaszil, György
%T Expressive capacity of subregular expressions
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2018
%P 201-218
%V 52
%N 2-3-4
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita/2018014/
%R 10.1051/ita/2018014
%G en
%F ITA_2018__52_2-3-4_201_0
Kutrib, Martin; Wendlandt, Matthias. Expressive capacity of subregular expressions. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 52 (2018) no. 2-3-4, pp. 201-218. doi : 10.1051/ita/2018014. http://www.numdam.org/articles/10.1051/ita/2018014/

[1] R.S. Cohen and J.A. Brzozowski, Dot-depth of star-free events. J. Comput. Syst. Sci. 5 (1971) 1–16 | DOI | MR | Zbl

[2] M. Fürer, The complexity of the inequivalence problem for regular expressions with intersection, in International Colloquium on Automata, Languages and Programming (ICALP 1980). Vol. 85 of Lect. Notes Comput. Sci. Springer, Berlin, Heidelberg (1980) 234–245 | DOI | MR | Zbl

[3] M. Holzer and M. Kutrib, The complexity of regular(-like) expressions. Int. J. Found. Comput. Sci. 22 (2011) 1533–1548 | DOI | MR | Zbl

[4] M. Holzer, M. Kutrib and K. Meckel, Nondeterministic state complexity of star-free languages. Theor. Comput. Sci. 450 (2012) 68–80 | DOI | MR | Zbl

[5] H.B. Hunt, Iii, The Equivalence Problem for Regular Expressions with Intersections is not Polynomial in Tape. Technical Report TR 73-161, Department of Computer Science, Cornell University (1973)

[6] S.C. Kleene, Representation of events in nerve nets and finite automata, in Automata Studies. Princeton University Press, NJ (1956) 3–42 | MR

[7] M. Kutrib and M. Wendlandt, Expressive capacity of concatenation freeness, in Implementation and Application of Automata (CIAA 2015). Vol. 9223 of Lect. Notes Comput. Sci. Springer, Cham (2015) 199–210 | MR | Zbl

[8] M. Kutrib and M. Wendlandt, Expressive capacity of subregular expressions, in Non-Classical Models of Automata and Applications (NCMA 2016). Vol. 321 of books@ocg.at. Austrian Computer Society, Vienna (2016) 227–242 | Numdam | MR | Zbl

[9] M. Kutrib and M. Wendlandt, Concatenation-free languages. Theor. Comput. Sci. 679 (2017) 83–94 | DOI | MR | Zbl

[10] R. Mcnaughton and S. Papert, Counter-Free Automata. Research Monographs no. 65. MIT Press, MA (1971) | MR | Zbl

[11] B. Nagy, A normal form for regular expressions, in Supplemental Papers for DLT 2004. In Vol. 252 of CDMTCS. University of Auckland, Centre for Discrete Mathematics and Theoretical Computer Science (2004) 1–10

[12] B. Nagy, Union-free regular languages and 1-cycle-free-path automata. Publ. Math. Debrecen 68 (2006) 183–197 | DOI | MR | Zbl

[13] H. Petersen, Decision problems for generalized regular expressions, in Descriptional Complexity of Automata, Grammars and Related Structures (DCAGRS 2000). London, Ontario (2000) 22–29

[14] H. Petersen, The membership problem for regular expressions with intersection is complete in LOGCFL, in Theoretical Aspects of Computer Science (STACS 2002). Vol. 2285 of Lect. Notes Comput. Sci. Springer, Berlin, Heidelberg (2002) 513–522 | MR | Zbl

[15] K. Salomaa and S. Yu, Alternating finite automata and star-free languages. Theor. Comput. Sci. 234 (2000) 167–176 | DOI | MR | Zbl

[16] M.-P. Schützenberger, On finite monoids having only trivial subgroups. Inform. Control 8 (1965) 190–194 | DOI | MR | Zbl

[17] J. Shallit, The frobenius problem and its generalizations, in Developments in Language Theory (DLT 2008). Vol. 5257 of Lect. Notes Comput. Sci. Springer, (2008) 72–83 | MR | Zbl

[18] L.J. Stockmeyer, The Complexity of Decision Problems in Automata Theory and Logic. Ph.D. thesis, Massachusetts Institute of Technology, MA (1974)

[19] L.J. Stockmeyer and A.R. Meyer, Word problems requiring exponential time, in Symposium on Theory of Computing (STOC 1973). ACM Press, NY (1973) 1–9 | MR | Zbl

[20] D. Werner, Erweiterte union-free Sprachen über unärem Alphabet. Bachelor’s thesis, Universität Giessen, Institut für Informatik, Germany (2013) (in German)

Cité par Sources :