Unrestricted State Complexity of Binary Operations on Regular Languages

Abstract : I study the state complexity of binary operations on regular languages over different alphabets. It is well known that if $$L'_m$$ and $$L_n$$ are languages restricted to be over the same alphabet, with m and n quotients, respectively, the state complexity of any binary boolean operation on $$L'_m$$ and $$L_n$$ is mn, and that of the product (concatenation) is $$(m-1)2^n +2^{n-1}$$. In contrast to this, I show that if $$L'_m$$ and $$L_n$$ are over their own different alphabets, the state complexity of union and symmetric difference is $$mn+m+n+1$$, that of intersection is $$mn+1$$, that of difference is $$mn+m+1$$, and that of the product is $$m2^n+2^{n-1}$$.
Type de document :
Communication dans un congrès
Cezar Câmpeanu; Florin Manea; Jeffrey Shallit. 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Jul 2016, Bucharest, Romania. Springer International Publishing, Lecture Notes in Computer Science, LNCS-9777, pp.60-72, 2016, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-41114-9_5〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01633951
Contributeur : Hal Ifip <>
Soumis le : lundi 13 novembre 2017 - 15:32:40
Dernière modification le : lundi 13 novembre 2017 - 15:35:35
Document(s) archivé(s) le : mercredi 14 février 2018 - 16:02:41

Fichier

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

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

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Janusz Brzozowski. Unrestricted State Complexity of Binary Operations on Regular Languages. Cezar Câmpeanu; Florin Manea; Jeffrey Shallit. 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Jul 2016, Bucharest, Romania. Springer International Publishing, Lecture Notes in Computer Science, LNCS-9777, pp.60-72, 2016, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-41114-9_5〉. 〈hal-01633951〉

Partager

Métriques

Consultations de la notice

36