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.
DOI : 10.1051/ita/2018014
Mots clés : Regular expressions, concatenation-free languages, star-free languages, union-free languages, expressive capacity, characterizations, closure properties, subregular hierarchy
@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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ita/2018014/
[1] and , Dot-depth of star-free events. J. Comput. Syst. Sci. 5 (1971) 1–16 | DOI | MR | Zbl
[2] , 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] and , The complexity of regular(-like) expressions. Int. J. Found. Comput. Sci. 22 (2011) 1533–1548 | DOI | MR | Zbl
[4] , and , Nondeterministic state complexity of star-free languages. Theor. Comput. Sci. 450 (2012) 68–80 | DOI | MR | Zbl
[5] , 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] , Representation of events in nerve nets and finite automata, in Automata Studies. Princeton University Press, NJ (1956) 3–42 | MR
[7] and , 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] and , 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] and , Concatenation-free languages. Theor. Comput. Sci. 679 (2017) 83–94 | DOI | MR | Zbl
[10] and , Counter-Free Automata. Research Monographs no. 65. MIT Press, MA (1971) | MR | Zbl
[11] , 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] , Union-free regular languages and 1-cycle-free-path automata. Publ. Math. Debrecen 68 (2006) 183–197 | DOI | MR | Zbl
[13] , Decision problems for generalized regular expressions, in Descriptional Complexity of Automata, Grammars and Related Structures (DCAGRS 2000). London, Ontario (2000) 22–29
[14] , 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] and , Alternating finite automata and star-free languages. Theor. Comput. Sci. 234 (2000) 167–176 | DOI | MR | Zbl
[16] , On finite monoids having only trivial subgroups. Inform. Control 8 (1965) 190–194 | DOI | MR | Zbl
[17] , 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] , The Complexity of Decision Problems in Automata Theory and Logic. Ph.D. thesis, Massachusetts Institute of Technology, MA (1974)
[19] and , Word problems requiring exponential time, in Symposium on Theory of Computing (STOC 1973). ACM Press, NY (1973) 1–9 | MR | Zbl
[20] , 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 :
