%0 Conference Proceedings
%T Cover Complexity of Finite Languages
%+ Vienna University of Technology = Technische Universität Wien (TU Wien)
%A Hetzl, Stefan
%A Wolfsteiner, Simon
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 20th International Conference on Descriptional Complexity of Formal Systems (DCFS)
%C Halifax, NS, Canada
%Y Stavros Konstantinidis
%Y Giovanni Pighizzini
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-10952
%P 139-150
%8 2018-07-25
%D 2018
%R 10.1007/978-3-319-94631-3_12
%Z Computer Science [cs]Conference papers
%X We consider the notion of cover complexity of finite languages on three different levels of abstraction. For arbitrary cover complexity measures, we give a characterisation of the situations in which they collapse to a bounded complexity measure. Moreover, we show for a restricted class of context-free grammars that its grammatical cover complexity measure w.r.t. a finite language L is unbounded and that the cover complexity of L can be computed from the exact complexities of a finite number of covers $$L' \supseteq L$$. We also investigate upper and lower bounds on the grammatical cover complexity of the language operations intersection, union, and concatenation on finite languages for several different types of context-free grammars.
%G English
%Z TC 1
%Z WG 1.2
%2 https://inria.hal.science/hal-01905625/document
%2 https://inria.hal.science/hal-01905625/file/470153_1_En_12_Chapter.pdf
%L hal-01905625
%U https://inria.hal.science/hal-01905625
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-WG1-2
%~ IFIP-LNCS-10952