Square on Deterministic, Alternating, and Boolean Finite Automata

Abstract : We investigate the state complexity of the square operation on languages represented by deterministic, alternating, and Boolean automata. For each k such that $1 \le k \le n-2$, we describe a binary language accepted by an n-state DFA with k final states meeting the upper bound $n2^n - k2^{n-1}$ on the state complexity of its square. We show that in the case of $k=n-1$, the corresponding upper bound cannot be met. Using the DFA witness for square with $2^n$ states where half of them are final, we get the tight upper bounds on the complexity of the square operation on alternating and Boolean automata.
Type de document :
Communication dans un congrès
Giovanni Pighizzini; Cezar Câmpeanu. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10316, pp.214-225, 2017, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-60252-3_17〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01657005
Contributeur : Hal Ifip <>
Soumis le : mercredi 6 décembre 2017 - 11:44:02
Dernière modification le : mercredi 6 décembre 2017 - 14:14:19

Fichier

 Accès restreint
Fichier visible le : 2020-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Ivana Krajňáková, Galina Jirásková. Square on Deterministic, Alternating, and Boolean Finite Automata. Giovanni Pighizzini; Cezar Câmpeanu. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10316, pp.214-225, 2017, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-60252-3_17〉. 〈hal-01657005〉

Partager

Métriques

Consultations de la notice

11