# Cover Complexity of Finite Languages

Abstract : 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.
Document type :
Conference papers
Domain :

Cited literature [23 references]

https://hal.inria.fr/hal-01905625
Contributor : Hal Ifip <>
Submitted on : Friday, October 26, 2018 - 8:01:05 AM
Last modification on : Friday, October 26, 2018 - 8:05:10 AM
Long-term archiving on : Sunday, January 27, 2019 - 12:34:27 PM

### File

##### Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2021-01-01

### Citation

Stefan Hetzl, Simon Wolfsteiner. Cover Complexity of Finite Languages. 20th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2018, Halifax, NS, Canada. pp.139-150, ⟨10.1007/978-3-319-94631-3_12⟩. ⟨hal-01905625⟩

Record views