×

zbMATH — the first resource for mathematics

Deciding determinism of unary languages. (English) Zbl 1332.68122
Summary: In this paper, we investigate the complexity of deciding determinism of unary languages. First, we give a method to derive a set of arithmetic progressions from a regular expression \(E\) over a unary alphabet, and establish relations between numbers represented by these arithmetic progressions and words in \(\mathcal{L}(E)\). Next, we define a problem relating to arithmetic progressions and investigate the complexity of this problem. Then by a reduction from this problem we show that deciding determinism of unary languages is coNP-complete. Finally, we extend our derivation method to expressions with counting, and prove that deciding whether an expression over a unary alphabet with counting defines a deterministic language is in \(\Pi_2^{\mathrm p}\). We also establish a tight upper bound for the size of the minimal DFA for expressions with counting.

MSC:
68Q45 Formal languages and automata
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
Software:
ALGOL 60
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Amer-Yahia, S.; Kotidis, Y., A web-services architecture for efficient XML data exchange, (Proceedings of the 20th International Conference on Data Engineering, (2004), IEEE), 523-534
[2] Bourret, R., XML and databases, (2000)
[3] Gao, S.; Sperberg-McQueen, C. M.; Thompson, H. S.; Mendelsohn, N.; Beech, D.; Maloney, M., W3C XML schema definition language (XSD) 1.1 part 1: structures, (2012)
[4] Bex, G. J.; Neven, F.; Van den Bussche, J., DTDs versus XML schema: a practical study, (Proceedings of the 7th International Workshop on the Web and Databases: Colocated with ACM SIGMOD/PODS 2004, (2004), ACM), 79-84
[5] Martens, W.; Neven, F.; Schwentick, T.; Bex, G. J., Expressiveness and complexity of XML schema, ACM Trans. Database Syst., 31, 3, 770-813, (2006)
[6] W. W. W. Consortium
[7] van der Vlist, E., XML schema, (2002), O’Reilly Media, Inc. · Zbl 1001.68026
[8] Bex, G. J.; Gelade, W.; Martens, W.; Neven, F., Simplifying XML schema: effortless handling of nondeterministic regular expressions, (Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, (2009), ACM), 731-744
[9] Brüggemann-Klein, A.; Wood, D., One-unambiguous regular languages, Inf. Comput., 140, 2, 229-253, (1998) · Zbl 0895.68146
[10] Brüggemann-Klein, A., Regular expressions into finite automata, Theor. Comput. Sci., 120, 2, 197-213, (1993) · Zbl 0811.68096
[11] Groz, B.; Maneth, S.; Staworko, S., Deterministic regular expressions in linear time, (Proceedings of the 31st Symposium on Principles of Database Systems, (2012), ACM), 49-60
[12] Kilpeläinen, P., Checking determinism of XML schema content models in optimal time, Inf. Syst., 36, 3, 596-617, (2011)
[13] Chen, H.; Lu, P., Assisting the design of XML schema: diagnosing nondeterministic content models, (Web Technologies and Applications, (2011), Springer), 301-312
[14] Losemann, K.; Martens, W.; Niewerth, M., Descriptional complexity of deterministic regular expressions, (Mathematical Foundations of Computer Science 2012, (2012), Springer), 643-654 · Zbl 1338.68153
[15] Chen, H.; Lu, P., Checking determinism of regular expressions with counting, Inf. Comput., 241, 302-320, (2015) · Zbl 1330.68151
[16] Czerwiński, W.; David, C.; Losemann, K.; Martens, W., Deciding definability by deterministic regular expressions, (Foundations of Software Science and Computation Structures, (2013), Springer), 289-304 · Zbl 1260.68199
[17] Lu, P.; Bremer, J.; Chen, H., Deciding determinism of regular languages, Theory Comput. Syst., 57, 1, 97-139, (2015) · Zbl 1339.68151
[18] Latte, M.; Niewerth, M., Definability by weakly deterministic regular expressions with counters is decidable, (Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science 2015, Part I, MFCS 2015, Milan, Italy, August 24-28, 2015, (2015)), 369-381 · Zbl 06482749
[19] Gelade, W.; Gyssens, M.; Martens, W., Regular expressions with counting: weak versus strong determinism, SIAM J. Comput., 41, 1, 160-190, (2012) · Zbl 1252.68146
[20] Kilpeläinen, P.; Tuhkanen, R., Regular expressions with numerical occurrence indicators-preliminary results, (SPLST, (2003)), 163-173
[21] Gelade, W., Succinctness of regular expressions with interleaving, intersection and counting, Theor. Comput. Sci., 411, 31, 2987-2998, (2010) · Zbl 1192.68120
[22] Hopcroft, J. E.; Motwani, R.; Ullman, J. D., Introduction to automata theory, languages, and computation, (2007), Pearson
[23] Chrobak, M., Finite automata and unary languages, Theor. Comput. Sci., 47, 149-158, (1986) · Zbl 0638.68096
[24] Rich, E., Automata, computability and complexity: theory and applications, (2008), Pearson Prentice Hall Upper Saddle River
[25] Ginsburg, S.; Rice, H. G., Two families of languages related to ALGOL, J. ACM, 9, 3, 350-371, (1962) · Zbl 0196.01803
[26] Graham, R. L.; Knuth, D. E.; Patashnik, O., Concrete mathematics: A foundation for computer science, (1994) · Zbl 0836.00001
[27] Brauer, A., On a problem of partitions, Am. J. Math., 299-312, (1942) · Zbl 0061.06801
[28] Pighizzini, G.; Shallit, J.; Wang, M.-w., Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds, J. Comput. Syst. Sci., 65, 2, 393-414, (2002) · Zbl 1059.68068
[29] K. Bickel, M. Firrisa, J. Ortiz, K. Pueschel, Constructions of Coverings of the Integers: Exploring an Erdős Problem, Summer Math Institute, Cornell University.
[30] Erdős, P., On integers of the form \(2^k + p\) and some related problems, Summa Bras. Math., 2, 113-123, (1950)
[31] Guy, R., Unsolved problems in number theory, vol. 1, (2004), Springer Science & Business Media
[32] Stockmeyer, L. J.; Meyer, A. R., Word problems requiring exponential time, (Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, (1973), ACM), 1-9, (preliminary report) · Zbl 0359.68050
[33] Michael, R. G.; David, S. J., Computers and intractability: a guide to the theory of NP-completeness, (1979) · Zbl 0411.68039
[34] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to algorithms, vol. 2, (2001), MIT Press Cambridge
[35] Sawa, Z., Efficient construction of semilinear representations of languages accepted by unary NFA, (Reachability Problems, (2010), Springer), 176-182 · Zbl 1287.68100
[36] Schnitger, G., Regular expressions and NFAs without ε-transitions, (STACS 2006, (2006), Springer), 432-443 · Zbl 1136.68422
[37] Holzer, M.; Kutrib, M., The complexity of regular (-like) expressions, Int. J. Found. Comput. Sci., 22, 07, 1533-1548, (2011) · Zbl 1252.68174
[38] Steen, L. A.; Seebach, J. A.; Steen, L. A., Counterexamples in topology, (1978), Springer · Zbl 0211.54401
[39] Han, Y.-S.; Salomaa, K.; Wood, D., Prime decompositions of regular languages, (Developments in Language Theory, (2006), Springer), 145-155 · Zbl 1227.68057
[40] Groz, B., XML security views: queries, updates and schemas, (2012), University Lille 1, Ph.D. thesis
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.