While the closure of a language family LL under certain language operations is the least family of languages which contains all members of LL and is closed under all of the operations, a kernel of LL is a maximal family of languages which is a sub-family of LL and is closed under all of the operations. Here we investigate properties of the Boolean kernels of the family of context-free languages. Additionally, languages that are mandatory for each Boolean kernel and languages that are optional for Boolean kernels are studied. That is, we consider the intersection of all Boolean kernels as well as their union. The expressive capacities of these families are addressed leading to a hierarchical structure. Further closure properties are considered. Furthermore, we study descriptional complexity aspects of these families, where languages are represented by context-free grammars with proofs attached. It turns out that the size trade-offs between all families in question and deterministic context-free languages are non-recursive. That is, one can choose an arbitrarily large recursive function f, but the gain in economy of description eventually exceeds f when changing from the latter system to the former.
Boolean Kernels of Context-Free Languages / M. Kutrib, L. Prigioniero (LECTURE NOTES IN ARTIFICIAL INTELLIGENCE). - In: Implementation and Application of Automata / [a cura di] S. Maneth. - [s.l] : Springer, 2021. - ISBN 9783030791209. - pp. 152-164 (( Intervento presentato al 25. convegno CIAA tenutosi a Virtual Event nel 2021 [10.1007/978-3-030-79121-6_13].
|Titolo:||Boolean Kernels of Context-Free Languages|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Data di pubblicazione:||2021|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1007/978-3-030-79121-6_13|
|Tipologia:||Book Part (author)|
|Appare nelle tipologie:||03 - Contributo in volume|
File in questo prodotto:
|ciaa-submission.pdf||Post-print, accepted manuscript ecc. (versione accettata dall'editore)||Administrator Richiedi una copia|
|Kutrib-Prigioniero2021_Chapter_BooleanKernelsOfContext-FreeLa.pdf||Publisher's version/PDF||Administrator Richiedi una copia|