Skip to Main content Skip to Navigation
Conference papers

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
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Friday, October 26, 2018 - 8:01:05 AM
Last modification on : Wednesday, November 3, 2021 - 4:18:26 AM
Long-term archiving on: : Sunday, January 27, 2019 - 12:34:27 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



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


Files downloads