Article

Descriptional complexity of deterministic regular expressions

Authors:

Katja Losemann,

Matthias NiewerthAuthors Info & Claims

MFCS'12: Proceedings of the 37th international conference on Mathematical Foundations of Computer Science

Pages 643 - 654

https://doi.org/10.1007/978-3-642-32589-2_56

Published: 27 August 2012 Publication History

Abstract

We study the descriptional complexity of regular languages that are definable by deterministic regular expressions. First, we examine possible blow-ups when translating between regular expressions, deterministic regular expressions, and deterministic automata. Then we give an overview of the closure properties of these languages under various language-theoretic operations and we study the descriptional complexity of applying these operations. Our main technical result is a general property that implies that the blow-up when translating a DFA to an equivalent deterministic expression can be exponential.

References

[1]

Bex, G. J., Gelade, W., Martens, W., Neven, F.: Simplifying XML Schema: effortless handling of nondeterministic regular expressions. In: SIGMOD (2009)

Digital Library

[2]

Brüggemann-Klein, A., Wood, D.: One-unambiguous regular languages. Information and Computation 142(2), 182-206 (1998)

Digital Library

[3]

Câmpeanu, C., Culik, K., Salomaa, K., Yu, S.: State Complexity of Basic Operations on Finite Languages. In: Boldt, O., Jürgensen, H. (eds.) WIA 1999. LNCS, vol. 2214, pp. 60-70. Springer, Heidelberg (2001)

Digital Library

[4]

Caron, P., Han, Y.-S., Mignot, L.:Generalized One-Unambiguity. In:Mauri, G., Leporati, A. (eds.) DLT 2011. LNCS, vol. 6795, pp. 129-140. Springer, Heidelberg (2011)

Digital Library

[5]

Ehrenfeucht, A., Zeiger, H.: Complexity measures for regular expressions. JCSS 12(2), 134-146 (1976)

Digital Library

[6]

Ellul, K., Krawetz, B., Shallit, J., Wang, M.: Regular expressions: new results and open problems. In: JALC, pp. 233-256 (2004)

Digital Library

[7]

Gelade, W., Idziaszek, T., Martens, W., Neven, F.: Simplifying XML Schema: Single-type approximations of regular tree languages. In: PODS (2010)

Digital Library

[8]

Gelade, W., Neven, F.: Succinctness of the complement and intersection of regular expressions. In: TOCL, pp. 4:1-4:19 (2012)

Digital Library

[9]

Gruber, H., Holzer, M.: Finite Automata, Digraph Connectivity, and Regular Expression Size. In: Aceto, L., Damgård, I., Goldberg, L. A., Halldórsson, M. M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 39-50. Springer, Heidelberg (2008)

Digital Library

[10]

Gruber, H., Holzer, M.: Tight Bounds on the Descriptional Complexity of Regular Expressions. In: Diekert, V., Nowotka, D. (eds.) DLT 2009. LNCS, vol. 5583, pp. 276-287. Springer, Heidelberg (2009)

Digital Library

[11]

Gruber, H., Johannsen, J.: Optimal Lower Bounds on Regular Expression Size Using Communication Complexity. In: Amadio, R. M. (ed.) FOSSACS 2008. LNCS, vol. 4962, pp. 273-286. Springer, Heidelberg (2008)

Digital Library

[12]

Hopcroft, J. E., Motwani, R., Ullman, J. D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (2007)

Digital Library

[13]

Jirásek, J., Jirásková, G., Szabari, A.: State Complexity of Concatenation and Complementation of Regular Languages. In: Domaratzki, M., Okhotin, A., Salomaa, K., Yu, S. (eds.) CIAA 2004. LNCS, vol. 3317, pp. 178-189. Springer, Heidelberg (2005)

Digital Library

[14]

Jirásková, G.: On the State Complexity of Complements, Stars, and Reversals of Regular Languages. In: Ito, M., Toyama, M. (eds.) DLT 2008. LNCS, vol. 5257, pp. 431-442. Springer, Heidelberg (2008)

Digital Library

[15]

Kintala, C., Wotschke, D.: Amounts of nondeterminism in finite automata. Acta Informatica 13, 199-204 (1980)

[16]

Losemann, K.: Boolesche Operationen auf deterministischen regulären Ausdrücken. Master's thesis, TU Dortmund (October 2010)

[17]

Martens, W., Niewerth, M., Schwentick, T.: Schema design for XML repositories: Complexity and tractability. In: PODS (2010)

Digital Library

[18]

Pighizzini, G., Shallit, J.: Unary language operations, state complexity and Jacobsthal's function. In: IJFCS, pp. 145-159 (2002)

[19]

Salomaa, A., Wood, D., Yu, S.: On the state complexity of reversals of regular languages. In: TCS, pp. 315-329 (2004)

Digital Library

[20]

Yu, S.: State complexity of regular languages. In: JALC, p. 221 (2001)

Digital Library

[21]

Yu, S., Zhuang, Q., Salomaa, K.: The state complexities of some basic operations on regular languages. In: TCS, pp. 315-328 (1994)

Digital Library

Cited By

Martens WNeven FNiewerth MSchwentick T(2017)BonXaiACM Transactions on Database Systems10.1145/310596042:3(1-42)Online publication date: 24-Aug-2017
https://dl.acm.org/doi/10.1145/3105960
Martens WNeven FNiewerth MSchwentick TMilo TCalvanese D(2015)BonXaiProceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/2745754.2745774(145-156)Online publication date: 20-May-2015
https://dl.acm.org/doi/10.1145/2745754.2745774
Lu PPeng FChen HZheng L(2015)Deciding determinism of unary languagesInformation and Computation10.1016/j.ic.2015.08.005245:C(181-196)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1016/j.ic.2015.08.005
Show More Cited By

Descriptional complexity of deterministic regular expressions
1. Software and its engineering
  1. Software notations and tools
2. Theory of computation
  1. Formal languages and automata theory

Recommendations

Closure properties and descriptional complexity of deterministic regular expressions

We study the descriptional complexity of regular languages that are definable by deterministic regular expressions, i.e., we examine worst-case blow-ups in size when translating between different representations for such languages. As representations of ...
Descriptional complexity of unambiguous input-driven pushdown automata

It is known that a nondeterministic input-driven pushdown automaton (IDPDA) (a.k.a. visibly pushdown automaton; a.k.a. nested word automaton) with n states can be transformed to an equivalent deterministic automaton with 2 ( n 2 ) states (B. von ...
Descriptional complexity of limited automata

A k-limited automaton is a linear bounded automaton that may rewrite each tape cell only in the first k visits, where k0 is a fixed constant. It is known that these automata accept context-free languages only. We investigate the descriptional complexity ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

MFCS'12: Proceedings of the 37th international conference on Mathematical Foundations of Computer Science

August 2012

835 pages

ISBN:9783642325885

Editors:
Branislav Rovan
Department of Computer Science, Comenius University, Mlynska Dolina, Bratislava, Slovakia
,
Vladimiro Sassone
Department of Electronics and Computer Science, University of Southampton, Mlynska Dolina, Southampton, UK
,
Peter Widmayer
Institute of Theoretical Computer Science, ETH Zürich, CAB H 39.2, Universitätstrasse 6, Zürich, Switzerland

Sponsors

Comenius University: Comenius University
Slovak Soc for Com Sci: Slovak Society for Computer Science
EATCS: European Association for Theoretical Computer Science

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 27 August 2012

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Martens WNeven FNiewerth MSchwentick T(2017)BonXaiACM Transactions on Database Systems10.1145/310596042:3(1-42)Online publication date: 24-Aug-2017
https://dl.acm.org/doi/10.1145/3105960
Martens WNeven FNiewerth MSchwentick TMilo TCalvanese D(2015)BonXaiProceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/2745754.2745774(145-156)Online publication date: 20-May-2015
https://dl.acm.org/doi/10.1145/2745754.2745774
Lu PPeng FChen HZheng L(2015)Deciding determinism of unary languagesInformation and Computation10.1016/j.ic.2015.08.005245:C(181-196)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1016/j.ic.2015.08.005
Czerwiński WDavid CLosemann KMartens W(2013)Deciding definability by deterministic regular expressionsProceedings of the 16th international conference on Foundations of Software Science and Computation Structures10.1007/978-3-642-37075-5_19(289-304)Online publication date: 16-Mar-2013
https://dl.acm.org/doi/10.1007/978-3-642-37075-5_19

View Options

View options

Media

Figures

Other

Tables

View Table of Contents