Top

Theory of Computing Systems

Published in:

26-03-2018

Primitivity, Uniform Minimality, and State Complexity of Boolean Operations

Author: Sylvie Davies

Published in: Theory of Computing Systems | Issue 8/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

A minimal deterministic finite automaton (DFA) is uniformly minimal if it always remains minimal when the final state set is replaced by a non-empty proper subset of the state set. We prove that a permutation DFA is uniformly minimal if and only if its transition monoid is a primitive group. We use this to study Boolean operations on group languages, which are recognized by direct products of permutation DFAs. A direct product cannot be uniformly minimal, except in the trivial case where one of the DFAs in the product is a one-state DFA. However, non-trivial direct products can satisfy a weaker condition we call uniform Boolean minimality, where only final state sets used to recognize Boolean operations are considered. We give sufficient conditions for a direct product of two DFAs to be uniformly Boolean minimal, which in turn gives sufficient conditions for pairs of group languages to have maximal state complexity under all binary Boolean operations (“maximal Boolean complexity”). In the case of permutation DFAs with one final state, we give necessary and sufficient conditions for pairs of group languages to have maximal Boolean complexity. Our results demonstrate a connection between primitive groups and automata with strong minimality properties.

previous article Polynomial Kernels for Vertex Cover Parameterized by Small Degree Modulators

next article Online Bin Packing with Advice of Small Size

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Almeida, J., Rodaro, E.: Semisimple synchronizing automata and the Wedderburn-Artin theory. Int. J. Found. Comput. Sc. 27(02), 127–145 (2016). https://doi.org/10.1142/S0129054116400037 MathSciNetCrossRefMATH

Araújo, J., Cameron, P.J., Steinberg, B.: Between primitive and 2-transitive: synchronization and its friends. arXiv:1511.03184 (2015)

Bell, J., Brzozowski, J., Moreira, N., Reis, R.: Symmetric groups and quotient complexity of boolean operations. In: Esparza, J., et al. (eds.) ICALP 2014, LNCS, vol. 8573, pp 1–12. Springer (2014). https://doi.org/10.1007/978-3-662-43951-7_1

Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system I: The user language. J. Symbolic Comput. 24(3–4), 235–265 (1997). https://doi.org/10.1006/jsco.1996.0125 MathSciNetCrossRefMATH

Brzozowski, J.: Quotient complexity of regular languages. J. Autom. Lang. Comb. 15(1/2), 71–89 (2010). https://doi.org/10.4204/EPTCS.3.2 MathSciNetMATH

Brzozowski, J.: In search of most complex regular languages. Int. J. Found. Comput. Sci. 24(06), 691–708 (2013). https://doi.org/10.1142/S0129054113400133 MathSciNetCrossRefMATH

Brzozowski, J.: Unrestricted state complexity of binary operations on regular languages. In: Câmpeanu, C., Manea, F., Shallit, J. (eds.) DCFS 2016, LNCS, vol. 9777, pp 60–72. Springer (2016). https://doi.org/10.1007/978-3-319-41114-9_5

Brzozowski, J., Jirásková, G., Li, B.: Quotient complexity of ideal languages. Theoret. Comput. Sci. 470, 36–52 (2013). https://doi.org/10.1016/j.tcs.2012.10.055 MathSciNetCrossRefMATH

Brzozowski, J., Liu, B.: Quotient complexity of star-free languages. Int. J. Found. Comput. Sci. 23(06), 1261–1276 (2012). https://doi.org/10.1142/S0129054112400515 MathSciNetCrossRefMATH

10.

Brzozowski, J.A., Davies, S., Liu, B.Y.V.: Most complex regular ideal languages. Discret. Math. Theoret. Comput. Sci. 18(3). Paper #15. https://dmtcs.episciences.org/volume/view/id/184 (2016)

11.

Brzozowski, J.A., Sinnamon, C.: Unrestricted state complexity of binary operations on regular and ideal languages. J. Autom. Lang. Comb. 22(1–3), 29–59 (2017). https://doi.org/10.25596/jalc-2017-029 MathSciNetMATH

12.

Cameron, P.J.: Finite permutation groups and finite simple groups. Bull. London Math. Soc. 13(1), 1–22 (1981). https://doi.org/10.1112/blms/13.1.1 MathSciNetCrossRefMATH

13.

Delgado, M., Linton, S., Morais, J.: Automata – a GAP package, Version 1.13. http://cmup.fc.up.pt/cmup/mdelgado/automata/ (2011)

14.

Dixon, J.D., Mortimer, B.: Permutation groups. Springer, Berlin (1996). https://doi.org/10.1007/978-1-4612-0731-3 https://doi.org/10.1007/978-1-4612-0731-3 CrossRefMATH

15.

Dummit, D., Foote, R.: Abstract Algebra. Wiley, NY (2004)MATH

16.

Ésik, Z., Gao, Y., Liu, G., Yu, S.: Estimation of state complexity of combined operations. Theoret. Comput. Sci. 410(35), 3272–3280 (2009). https://doi.org/10.1016/j.tcs.2009.03.026 MathSciNetCrossRefMATH

17.

Gao, Y., Moreira, N., Reis, R., Yu, S.: A survey on operational state complexity. J. Autom. Lang. Comb. 21(4), 251–310 (2016). https://doi.org/10.25596/jalc-2016-251 MathSciNetMATH

18.

Gao, Y., Yu, S.: State complexity and approximation. Int. J. Found. Comput. Sci. 23(05), 1085–1098 (2012). https://doi.org/10.1142/S0129054112400461 MathSciNetCrossRefMATH

19.

The GAP Group: GAP – Groups, Algorithms, and Programming, Version 4.8.6 (2016). http://www.gap-system.org

20.

Kiraz, G.A.: Compressed storage of sparse finite-state transducers. In: Boldt, O., Jürgensen, H. (eds.) WIA 1999, LNCS, vol. 2214, pp 109–121. Springer (2001). https://doi.org/10.1007/3-540-45526-4_11

21.

Maslov, A.N.: Estimates of the number of states of finite automata. Dokl. Akad. Nauk SSSR 194, 1266–1268 (Russian) (1970). English translation: Soviet Math. Dokl. 11 (1970) 1373–1375

22.

Restivo, A., Vaglica, R.: Extremal minimality conditions on automata. Theor. Comput. Sci. 440–441, 73–84 (2012). https://doi.org/10.1016/j.tcs.2012.03.049 MathSciNetCrossRefMATH

23.

Restivo, A., Vaglica, R.: A graph theoretic approach to automata minimality. Theoret. Comput. Sci. 429, 282–291 (2012). https://doi.org/10.1016/j.tcs.2011.12.049 MathSciNetCrossRefMATH

24.

Salomaa, A., Salomaa, K., Yu, S.: State complexity of combined operations. Theoret. Comput. Sci. 383(2), 140–152 (2007). https://doi.org/10.1016/j.tcs.2007.04.015 MathSciNetCrossRefMATH

25.

Salomaa, A., Wood, D., Yu, S.: On the state complexity of reversals of regular languages. Theoret. Comput. Sci. 320(2), 315–329 (2004). https://doi.org/10.1016/j.tcs.2004.02.032 MathSciNetCrossRefMATH

26.

Steinberg, B.: A theory of transformation monoids: combinatorics and representation theory. arXiv:https://arxiv.org/abs/1004.2982 (2010)

27.

Yu, S., Zhuang, Q., Salomaa, K.: The state complexities of some basic operations on regular languages. Theor. Comput. Sci. 125(2), 315–328 (1994). https://doi.org/10.1016/0304-3975(92)00011-F MathSciNetCrossRefMATH

Title: Primitivity, Uniform Minimality, and State Complexity of Boolean Operations
Author: Sylvie Davies
Publication date: 26-03-2018
Publisher: Springer US
Published in: Theory of Computing Systems / Issue 8/2018
Print ISSN: 1432-4350
Electronic ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-018-9859-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 8/2018

Space Efficient Linear Time Algorithms for BFS, DFS and Applications

Approximation and Heuristic Algorithms for Computing Backbones in Asymmetric Ad-hoc Networks

Polynomial Kernels for Vertex Cover Parameterized by Small Degree Modulators

Reasoning About XML Constraints Based on XML-to-Relational Mappings

Parameterised Algorithms for Deletion to Classes of DAGs

Parameterized Complexity of Voter Control in Multi-Peaked Elections

Premium Partner