| HAL-Inria | Publications, software ... of Inria's scientists |
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.
Cited literature [23 references]
https://hal.inria.fr/hal-01905625
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
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
File
470153_1_En_12_Chapter.pdf
Files produced by the author(s)
Licence
Distributed under a Creative Commons Attribution 4.0 International License