zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Language operations with regular expressions of polynomial size. (English) Zbl 1176.68105
Summary: This work deals with questions regarding to what extent regularity-preserving language operations affect the descriptional complexity of regular expressions. Some language operations are identified which are feasible for regular expressions in the sense that the result of the operation can be represented as a regular expression of size polynomial in that of the operands. We prove that taking language quotients, in particular the prefix and suffix closures, of a regular set can incur at most a quadratic blow-up on the required expression size. The circular shift operation can cause only a cubic increase in size and at least a quadratic bloat can be necessary in the worst case.
MSC:
68Q45Formal languages and automata
References:
[1]Asveld, P. R. J.: Generating all circular shifts by context-free grammars in greibach normal form, International journal of foundations of computer science 18, No. 6, 1139-1149 (2007) · Zbl 1183.68321 · doi:10.1142/S0129054107005182
[2]Berry, G.; Sethi, R.: From regular expressions to deterministic automata, Theoretical computer science 48, No. 3, 117-126 (1986)
[3]Berstel, J.; Pin, J. E.: Local languages and the Berry–Sethi algorithm, Theoretical computer science 155, No. 2, 439-446 (1996) · Zbl 0872.68116 · doi:10.1016/0304-3975(95)00104-2
[4]Birget, J. -C.: Intersection and union of regular languages and state complexity, Information processing letters 43, 185-190 (1992) · Zbl 0763.68048 · doi:10.1016/0020-0190(92)90198-5
[5]Brzozowski, J. A.: Derivatives of regular expressions, Journal of the ACM 11, No. 4, 481-494 (1964) · Zbl 0225.94044 · doi:10.1145/321239.321249
[6]Champarnaud, J. -M.; Ziadi, D.: Canonical derivatives, partial derivatives and finite automaton constructions, Theoretical computer science 289, No. 1, 137-163 (2002) · Zbl 1061.68109 · doi:10.1016/S0304-3975(01)00267-5
[7]Cohen, R. S.; Brzozowski, J. A.: General properties of star height of regular events, Journal of computer and system sciences 4, No. 3, 260-280 (1970) · Zbl 0245.94038 · doi:10.1016/S0022-0000(70)80024-1
[8]N.G. De Bruijn, Acknowledgement of priority to C. Flye Sainte-Marie on the counting of circular arrangements of 2n zeros and ones that show each n-letter word exactly once, T.H.-Report 75-WSK-06, Technological University Eindhoven, 1975 · Zbl 0323.05119
[9]Ellul, K.; Krawetz, B.; Shallit, J.; Wang, M.: Regular expressions: new results and open problems, Journal of automata, languages and combinatorics 10, No. 4, 407-437 (2005) · Zbl 1143.68434
[10]Sainte-Marie, C. Flye: Solution to question nr. 48, L’intermédiaire des mathématiciens 1, 107-110 (1894)
[11]Gelade, W.; Neven, F.: Succinctness of the complement and intersection of regular expressions, Dagstuhl seminar Proceedings 08001, 325-336 (2008)
[12]Gruber, H.; Holzer, M.: Finding lower bounds for nondeterministic state complexity is hard (extended abstract), Lncs 4036, 363-374 (June 2006) · Zbl 1227.68056 · doi:10.1007/11779148_33
[13]Gruber, H.; Holzer, M.: Finite automata, digraph connectivity, and regular expression size, Lncs 5126, 39-50 (2008) · Zbl 1155.68418 · doi:10.1007/978-3-540-70583-3_4
[14]Gruber, H.; Holzer, M.; Kutrib, M.: More on the size of higman–haines sets: effective constructions, Lncs 4664, 193-204 (2008)
[15]Gruber, H.; Johannsen, J.: Optimal lower bounds on regular expression size using communication complexity, Lncs 4962, 273-286 (2008) · Zbl 1139.68033 · doi:10.1007/978-3-540-78499-9_20
[16]Holzer, M.; Salomaa, K.; Yu, S.: On the state complexity of k-entry deterministic finite automata, Journal of automata, languages and combinatorics 6, No. 4, 453-466 (2001) · Zbl 1050.68093
[17]Hromkovič, J.; Schnitger, G.: On the hardness of determining small nfa’s and of proving lower bounds on their sizes, Lncs 5257, 34-55 (2008) · Zbl 1159.68017 · doi:10.1007/978-3-540-85780-8_3
[18]Hopcroft, J. E.; Ullman, J. D.: Introduction to automata theory, languages and computation, (1979) · Zbl 0426.68001
[19]Ilie, L.; Yu, S.: Follow automata, Information and computation 186, No. 1, 140-162 (2003) · Zbl 1059.68063 · doi:10.1016/S0890-5401(03)00090-7
[20]Kappes, M.: Descriptional complexity of deterministic finite automata with multiple initial states, Journal of automata, languages and combinatorics 5, No. 3, 269-278 (2000) · Zbl 0965.68041
[21]A. Okhotin, On the state complexity of scattered substrings and superstrings, TUCS Technical Report No. 849, Turku Centre for Computer Science, 2007
[22]Okhotin, A.; Jirásková, G.: State complexity of cyclic shift, RAIRO theoretical informatics and applications 42, No. 2, 335-360 (2008)
[23]Ziadi, D.: Regular expression for a language without empty word, Theoretical computer science 163, No. 1–2, 309-315 (1996) · Zbl 0878.68080 · doi:10.1016/0304-3975(96)00028-X