# 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}$.
Keywords :
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〉
Domaine :

Littérature citée [11 références]

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

### 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〉

### Métriques

Consultations de la notice