Most Complex Non-returning Regular Languages

Abstract : A regular language L is non-returning if in the minimal deterministic finite automaton accepting it there are no transitions into the initial state. Eom, Han and Jirásková derived upper bounds on the state complexity of boolean operations and Kleene star, and proved that these bounds are tight using two different binary witnesses. They derived upper bounds for concatenation and reversal using three different ternary witnesses. These five witnesses use a total of six different transformations. We show that for each $n \geqslant 4$ there exists a ternary witness of state complexity n that meets the bound for reversal and that at least three letters are needed to meet this bound. Moreover, the restrictions of this witness to binary alphabets meet the bounds for product, star, and boolean operations. We also derive tight upper bounds on the state complexity of binary operations that take arguments with different alphabets. We prove that the maximal syntactic semigroup of a non-returning language has $(n-1)^n$ elements and requires at least $\left( {\begin{array}{c}n\\ 2\end{array}}\right) $ generators. We find the maximal state complexities of atoms of non-returning languages. Finally, we show that there exists a most complex non-returning language that meets the bounds for all these complexity measures.
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.89-101, 2017, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-60252-3_7〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01656998
Contributeur : Hal Ifip <>
Soumis le : mercredi 6 décembre 2017 - 11:43:38
Dernière modification le : mercredi 6 décembre 2017 - 14:05:23

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

Janusz Brzozowski, Sylvie Davies. Most Complex Non-returning Regular Languages. 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.89-101, 2017, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-60252-3_7〉. 〈hal-01656998〉

Partager

Métriques

Consultations de la notice

18