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 metadatas

Cited literature [23 references]  Display  Hide  Download

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

Please log in to resquest access to the document

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

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⟩

Share

Metrics

Record views

40