Abstract
We introduce a new measure on regular languages: their nondeterministic syntactic complexity. It is the least degree of any extension of the ‘canonical boolean representation’ of the syntactic monoid. Equivalently, it is the least number of states of any subatomic nondeterministic acceptor. It turns out that essentially all previous structural work on nondeterministic state-minimality computes this measure. Our approach rests on an algebraic interpretation of nondeterministic finite automata as deterministic finite automata endowed with semilattice structure. Crucially, the latter form a self-dual category.
Stefan Milius–Supported by Deutsche Forschungsgemeinschaft (DFG) under projects MI 717/5-2 and MI 717/7-1, and as part of the Research and Training Group 2475 “Cybercrime and Forensic Computing” (393541319/GRK2475/1-2019)
Henning Urbat–Supported by Deutsche Forschungsgemeinschaft (DFG) under proj. SCHR 1118/8-2
Chapter PDF
Similar content being viewed by others
References
Adámek, J., Myers, R.S., Urbat, H., Milius, S.: On continuous nondeterminism and state minimality. In: Proc. 30th Conference on the Mathematical Foundations of Programming Semantics (MFPS XXX). vol. 308, pp. 3–23 (2014)
Angluin, D.: Inference of reversible languages. J. ACM 29(3), 741–765 (1982)
Arbib, M.A., Manes, E.G.: Adjoint machines, state-behavior machines, and duality. Journal of Pure and Applied Algebra 6(3), 313–344 (1975)
Arbib, M.A., Manes, E.G.: Fuzzy machines in a category. Bulletin of the Australian Mathematical Society 13(2), 169–210 (1975)
Backhouse, R.: Factor theory and the unity of opposites. Journal of Logical and Algebraic Methods in Programming 85(5, Part 2), 824–846 (2016)
Brzozowski, J., Tamm, H.: Theory of átomata. Theoretical Computer Science 539, 13–27 (2014)
Brzozowski, J.A.: Derivatives of regular expressions. J. ACM 11(4), 481–494 (Oct 1964)
Chrobak, M.: Finite automata and unary languages. Theoretical Computer Science 47, 149–158 (1986)
Clemente, L., Mayr, R.: Efficient reduction of nondeterministic automata with application to language inclusion testing. Logical Methods in Computer Science Volume 15, Issue 1 (2019)
Conway, J.H.: Regular Algebra and Finite Machines. Printed in GB by William Clowes & Sons Ltd (1971)
De Wulf, M., Doyen, L., Henzinger, T.A., Raskin, J.F.: Antichains: A new algorithm for checking universality of finite automata. In: Ball, T., Jones, R.B. (eds.) Computer Aided Verification. pp. 17–30. Springer (2006)
Denis, F., Lemay, A., Terlutte, A.: Residual finite state automata. In: Ferreira, A., Reichel, H. (eds.) STACS 2001: 18th Annual Symposium on Theoretical Aspects of Computer Science Dresden, Germany, February 15–17, 2001 Proceedings. pp. 144–157. Springer Berlin Heidelberg, Berlin, Heidelberg (2001)
Gawrychowski, P.: Chrobak normal form revisited, with applications. In: Bouchou-Markhoff, B., Caron, P., Champarnaud, J.M., Maurel, D. (eds.) Implementation and Application of Automata. pp. 142–153. Springer Berlin Heidelberg, Berlin, Heidelberg (2011)
Geldenhuys, J., van der Merwe, B., van Zijl, L.: Reducing nondeterministic finite automata with SAT solvers. In: Yli-Jyrä, A., Kornai, A., Sakarovitch, J., Watson, B. (eds.) Finite-State Methods and Natural Language Processing. pp. 81–92. Springer Berlin Heidelberg, Berlin, Heidelberg (2010)
Goguen, J.A.: Discrete-time machines in closed monoidal categories. I. J. Comput. Syst. Sci. 10(1), 1–43 (1975)
Gramlich, G.: Probabilistic and nondeterministic unary automata. In: Proc. of Math. Foundations of Computer Science, Springer, LNCS 2747, 2003. pp.460–469. Springer (2003)
Grätzer, G.: General Lattice Theory. Birkhäuser Verlag, 2. edn. (1998)
Gruber, H., Holzer, M.: Finding lower bounds for nondeterministic state complexity is hard. In: Ibarra, O.H., Dang, Z. (eds.) Developments in Language Theory: 10th International Conference, DLT 2006, Santa Barbara, CA, USA, June 26-29, 2006. Proceedings. pp. 363–374. Springer Berlin Heidelberg, Berlin, Heidelberg (2006)
Horn, A., Kimura, N.: The category of semilattices. Algebra Univ. 1, 26–38 (1971)
Hromkovič, J., Seibert, S., Karhumäki, J., Klauck, H., Schnitger, G.: Communication complexity method for measuring nondeterminism in finite automata. Information and Computation 172(2), 202–217 (2002), http://www.sciencedirect.com/science/article/pii/S089054010193069X
Izhakian, Z., Rhodes, J., Steinberg, B.: Representation theory of finite semigroups over semirings. Journal of Algebra 336(1), 139–157 (2011)
Jiang, T., McDowell, E., Ravikumar, B.: The structure and complexity of minimal nfa’s over a unary alphabet. International Journal of Foundations of Computer Science 02(02), 163–182 (1991)
Jiang, T., Ravikumar, B.: Minimal NFA problems are hard. SIAM Journal on Computing 22(6), 1117–1141 (1993)
Jipsen, P.: Categories of algebraic contexts equivalent to idempotent semirings and domain semirings. In: Kahl, W., Griffin, T.G. (eds.) Relational and Algebraic Methods in Computer Science. pp. 195–206. Springer Berlin Heidelberg, Berlin, Heidelberg (2012)
Johnstone, P.T.: Stone spaces. Cambridge University Press (1982)
Kameda, T., Weiner, P.: On the state minimization of nondeterministic finite automata. IEEE Transactions on Computers C-19(7), 617–627 (1970)
Kschischang, F.R.: The trellis structure of maximal fixed-cost codes. IEEE Transactions on Information Theory 42(6), 1828–1838 (1996)
Latteux, M., Roos, Y., Terlutte, A.: Minimal NFA and biRFSA languages. RAIRO - Theoretical Informatics and Applications 43(2), 221–237 (2009)
Markowsky, G.: Primes, irreducibles and extremal lattices. Order 9, 265–290 (09 1992)
Myers, R.S.R.: Nondeterministic automata and JSL-dfas. CoRR abs/2007.06031 (2020), https://arxiv.org/abs/2007.06031
Myers, R.S.R.: Representing semilattices as relations. CoRR abs/2007.10277 (2020), https://arxiv.org/abs/2007.10277
Myers, R.S.R., Adámek, J., Milius, S., Urbat, H.: Coalgebraic constructions of canonical nondeterministic automata. Theoretical Computer Science 604, 81–101 (2015)
Pin, J.É.: Mathematical foundations of automata theory (September 2020), available at http://www.liafa.jussieu.fr/~jep/PDF/MPRI/MPRI.pdf
Pin, J.E.: On reversible automata. In: Simon, I. (ed.) LATIN ’92. pp. 401–416. Springer Berlin Heidelberg, Berlin, Heidelberg (1992)
Polák, L.: Syntactic semiring of a language. In: Sgall, J., Pultr, A., Kolman, P. (eds.) Mathematical Foundations of Computer Science 2001: 26thInternational Symposium, MFCS 2001 Mariánské Lázne, Czech Republic, August 27–31, 2001 Proceedings. pp. 611–620. Springer Berlin Heidelberg, Berlin, Heidelberg (2001)
Shankar, P., Dasgupta, A., Deshmukh, K., Rajan, B.: On viewing block codes as finite automata. Theoretical Computer Science 290(3), 1775–1797 (2003)
Tamm, H.: New interpretation and generalization of the Kameda-Weiner method. In: Chatzigiannakis, I., Mitzenmacher, M., Rabani, Y., Sangiorgi, D. (eds.) ICALP 2016, Rome, Italy. LIPIcs, vol. 55, pp. 116:1–116:12. SchlossDagstuhl - Leibniz-Zentrum für Informatik (2016)
Tamm, H., Ukkonen, E.: Bideterministic automata and minimal representations of regular languages. Theoretical Computer Science 328(1), 135–149 (2004)
van Heerdt, G., Moerman, J., Sammartino, M., Silva, A.: A (co)algebraic theory of succinct automata. Journal of Logical and Algebraic Methods in Programming 105, 112–125 (2019)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2021 The Author(s)
About this paper
Cite this paper
Myers, R.S.R., Milius, S., Urbat, H. (2021). Nondeterministic Syntactic Complexity. In: Kiefer, S., Tasson, C. (eds) Foundations of Software Science and Computation Structures. FOSSACS 2021. Lecture Notes in Computer Science(), vol 12650. Springer, Cham. https://doi.org/10.1007/978-3-030-71995-1_23
Download citation
DOI: https://doi.org/10.1007/978-3-030-71995-1_23
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-71994-4
Online ISBN: 978-3-030-71995-1
eBook Packages: Computer ScienceComputer Science (R0)