Descriptional Complexity of Bounded Regular Languages

Abstract : We investigate the descriptional complexity of the subregular language classes of (strongly) bounded regular languages. In the first part, we study the costs for the determinization of nondeterministic finite automata accepting strongly bounded regular languages. The upper bound for the costs is larger than the costs for determinizing unary regular languages, but lower than the costs for determinizing arbitrary regular languages. In the second part, we study for (strongly) bounded languages the deterministic operational state complexity of the Boolean operations as well as the operations reversal, concatenation, and iteration. In detail, we present upper and lower bounds and we develop for the proof of the lower bounds a tool that exploits the number of different colorings of cycles occurring in deterministic finite automata accepting bounded languages.
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.138-152, 2016, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-41114-9_11〉
Liste complète des métadonnées

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

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

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

Andrea Herrmann, Martin Kutrib, Andreas Malcher, Matthias Wendlandt. Descriptional Complexity of Bounded 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.138-152, 2016, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-41114-9_11〉. 〈hal-01633949〉

Partager

Métriques

Consultations de la notice

41