More Web Proxy on the site http://driver.im/

research-article

Closure properties and descriptional complexity of deterministic regular expressions

Authors:

Katja Losemann,

Matthias NiewerthAuthors Info & Claims

Theoretical Computer Science, Volume 627, Issue C

Pages 54 - 70

https://doi.org/10.1016/j.tcs.2016.02.027

Published: 09 May 2016 Publication History

Abstract

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 languages, we consider regular expressions, deterministic regular expressions, and deterministic finite automata. Our results show that exponential blow-ups between these representations cannot be avoided. Furthermore, we study the descriptional complexity of these representations when applying boolean operations. Here, we start by investigating the closure properties of such languages under various language-theoretic operations such as union, intersection, concatenation, Kleene star, and reversal. Our results show that languages that are definable by deterministic regular expressions are not closed under any of these operations. Finally, we show that for all these operations except the Kleene star an exponential blow-up in the size of deterministic regular expressions cannot be avoided.

References

[1]

G.J. Bex, W. Gelade, W. Martens, F. Neven, Simplifying XML Schema: effortless handling of nondeterministic regular expressions, in: Proceedings of the International Conference on Management of Data, ACM, 2009, pp. 731-744.

[2]

A. Brüggemann-Klein, D. Wood, One-unambiguous regular languages, Inform. and Comput., 142 (1998) 182-206.

Digital Library

[3]

C. Câmpeanu, K. Culik, K. Salomaa, S. Yu, State complexity of basic operations on finite languages, in: Proceedings of the International Workshop on Implementing Automata, Springer, 2001, pp. 60-70.

[4]

P. Caron, Y. Han, L. Mignot, Generalized one-unambiguity, in: Proceedings of the International Conference on Developments in Language Theory, Springer, 2011, pp. 129-140.

[5]

H. Chen, P. Lu, Checking determinism of regular expressions with counting, Inform. and Comput., 241 (2015) 302-320.

Digital Library

[6]

W. Czerwiński, C. David, K. Losemann, W. Martens, Deciding definability by deterministic regular expressions, in: Proceedings of the International Conference on Foundations of Software Science and Computation Structures, 2013, pp. 289-304.

[7]

A. Ehrenfeucht, H. Zeiger, Complexity measures for regular expressions, J. Comput. System Sci., 12 (1976) 134-146.

Digital Library

[8]

K. Ellul, B. Krawetz, J. Shallit, M. Wang, Regular expressions: new results and open problems, J. Autom. Lang. Comb., 9 (2004) 233-256.

Digital Library

[9]

W. Gelade, T. Idziaszek, W. Martens, F. Neven, J. Paredaens, Simplifying XML schema: single-type approximations of regular tree languages, J. Comput. System Sci., 79 (2013) 910-936.

Digital Library

[10]

W. Gelade, F. Neven, Succinctness of the complement and intersection of regular expressions, ACM Trans. Comput. Log., 13 (2012) 4.

Digital Library

[11]

W. Gelade, M. Gyssens, W. Martens, Regular expressions with counting: weak versus strong determinism, SIAM J. Comput., 41 (2012) 160-190.

Digital Library

[12]

B. Groz, S. Maneth, S. Staworko, Deterministic regular expressions in linear time, in: Proceedings of the Symposium on Principles of Database Systems, 2012, pp. 49-60.

[13]

H. Gruber, M. Holzer, Finite automata, digraph connectivity, and regular expression size, in: Proceedings of the International Colloquium on Automata, Languages and Programming, Springer, 2008, pp. 39-50.

[14]

H. Gruber, M. Holzer, Tight bounds on the descriptional complexity of regular expressions, in: Proceedings of the International Conference on Developments in Language Theory, Springer, 2009, pp. 276-287.

[15]

H. Gruber, J. Johannsen, Optimal lower bounds on regular expression size using communication complexity, in: Proceedings of the International Conference on Foundations of Software Science and Computational Structures, Springer, 2008, pp. 273-286.

[16]

J.E. Hopcroft, R. Motwani, J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, Pearson Education, 2007.

[17]

D. Hovland, Regular expressions with numerical constraints and automata with counters, in: International Colloquium on Theoretical Aspects of Computing, Springer, 2009, pp. 231-245.

[18]

J. Jirásek, G. Jirásková, A. Szabari, State complexity of concatenation and complementation of regular languages, in: Proceedings of the International Conference on Implementation and Application of Automata, 2004.

[19]

G. Jirásková, On the state complexity of complements, stars, and reversals of regular languages, in: Proceedings of the International Conference on Developments in Language Theory, Springer, 2008, pp. 431-442.

[20]

P. Kilpeläinen, Checking determinism of XML Schema content models in optimal time, Inform. Sci., 36 (2011) 596-617.

Digital Library

[21]

P. Kilpeläinen, R. Tuhkanen, One-unambiguity of regular expressions with numeric occurrence indicators, Inform. and Comput., 205 (2007) 890-916.

Digital Library

[22]

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

Digital Library

[23]

M. Latte, M. Niewerth, Definability by weakly deterministic regular expressions with counters is decidable, in: Proceedings of the International Symposium on Mathematical Foundations of Computer Science, 2015, pp. 369-381.

[24]

K. Losemann, Boolesche Operationen auf deterministischen regulären Ausdrücken, TU Dortmund, October 2010.

[25]

K. Losemann, W. Martens, M. Niewerth, Descriptional complexity of deterministic regular expressions, in: Proceedings of the International Symposium on Mathematical Foundations of Computer Science, Springer, 2012, pp. 643-654.

[26]

P. Lu, J. Bremer, H. Chen, Deciding determinism of regular languages, Theory Comput. Syst., 57 (2015) 97-139.

Digital Library

[27]

P. Lu, F. Peng, H. Chen, L. Zheng, Deciding determinism of unary languages, Inform. and Comput., 245 (2015) 181-196.

Digital Library

[28]

R. Mandl, Precise bounds associated with the subset construction on various classes of nondeterminism finite automata, in: Proceedings of the Annual Princeton Conference on Information Science and Systems, Princeton University Press, 1973, pp. 263-267.

[29]

W. Martens, M. Niewerth, T. Schwentick, Schema design for XML repositories: complexity and tractability, in: Proceedings of the Symposium on Principles of Database Systems, ACM, 2010.

[30]

G. Pighizzini, J. Shallit, Unary language operations, state complexity and Jacobsthal's function, Internat. J. Found. Comput. Sci., 13 (2002) 145-159.

[31]

A. Salomaa, D. Wood, S. Yu, On the state complexity of reversals of regular languages, Theoret. Comput. Sci., 320 (2004) 315-329.

Digital Library

[32]

K. Salomaa, S. Yu, NFA to DFA transformation for finite languages over arbitrary alphabets, J. Autom. Lang. Comb., 2 (1997) 177-186.

[33]

S. Yu, State complexity of regular languages, J. Autom. Lang. Comb., 6 (2001) 221.

Digital Library

[34]

S. Yu, Q. Zhuang, K. Salomaa, The state complexities of some basic operations on regular languages, Theoret. Comput. Sci., 125 (1994) 315-328.

Digital Library

Cited By

Martens WLibkin LBarceló P(2022)Towards Theory for Real-World DataProceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3517804.3526066(261-276)Online publication date: 12-Jun-2022
https://dl.acm.org/doi/10.1145/3517804.3526066
Li YChen HZhang LHuang BZhang J(2020)Inferring Restricted Regular Expressions with Interleaving from Positive and Negative SamplesAdvances in Knowledge Discovery and Data Mining10.1007/978-3-030-47436-2_58(769-781)Online publication date: 11-May-2020
https://dl.acm.org/doi/10.1007/978-3-030-47436-2_58
Beedkar KGemulla RMartens W(2019)A Unified Framework for Frequent Sequence Mining with Subsequence ConstraintsACM Transactions on Database Systems10.1145/332148644:3(1-42)Online publication date: 5-Jun-2019
https://dl.acm.org/doi/10.1145/3321486
Show More Cited By

Closure properties and 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

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 deterministic regular expressions
MFCS'12: Proceedings of the 37th international conference on Mathematical Foundations of Computer Science

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 ...
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 Theoretical Computer Science

Theoretical Computer Science Volume 627, Issue C

May 2016

118 pages

ISSN:0304-3975

Issue’s Table of Contents

Copyright © Elsevier B.V.

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 09 May 2016

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Martens WLibkin LBarceló P(2022)Towards Theory for Real-World DataProceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3517804.3526066(261-276)Online publication date: 12-Jun-2022
https://dl.acm.org/doi/10.1145/3517804.3526066
Li YChen HZhang LHuang BZhang J(2020)Inferring Restricted Regular Expressions with Interleaving from Positive and Negative SamplesAdvances in Knowledge Discovery and Data Mining10.1007/978-3-030-47436-2_58(769-781)Online publication date: 11-May-2020
https://dl.acm.org/doi/10.1007/978-3-030-47436-2_58
Beedkar KGemulla RMartens W(2019)A Unified Framework for Frequent Sequence Mining with Subsequence ConstraintsACM Transactions on Database Systems10.1145/332148644:3(1-42)Online publication date: 5-Jun-2019
https://dl.acm.org/doi/10.1145/3321486
Li YMou XChen H(2019)Learning k-Occurrence Regular Expressions from Positive and Negative SamplesConceptual Modeling10.1007/978-3-030-33223-5_22(264-272)Online publication date: 4-Nov-2019
https://dl.acm.org/doi/10.1007/978-3-030-33223-5_22
Mou XChen HLi Y(2019)Context-Free Grammars for Deterministic Regular Expressions with InterleavingTheoretical Aspects of Computing – ICTAC 201910.1007/978-3-030-32505-3_14(235-252)Online publication date: 31-Oct-2019
https://dl.acm.org/doi/10.1007/978-3-030-32505-3_14

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents