%0 Conference Proceedings
%T Descriptional Complexity of Bounded Regular Languages
%+ Justus-Liebig-Universität Gießen = Justus Liebig University (JLU)
%A Herrmann, Andrea
%A Kutrib, Martin
%A Malcher, Andreas
%A Wendlandt, Matthias
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS)
%C Bucharest, Romania
%Y Cezar Câmpeanu
%Y Florin Manea
%Y Jeffrey Shallit
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-9777
%P 138-152
%8 2016-07-05
%D 2016
%R 10.1007/978-3-319-41114-9_11
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 1
%Z WG 1.2
%2 https://inria.hal.science/hal-01633949/document
%2 https://inria.hal.science/hal-01633949/file/416473_1_En_11_Chapter.pdf
%L hal-01633949
%U https://inria.hal.science/hal-01633949
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-LNCS-9777
%~ IFIP-WG1-2