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].
Boolean Kernels of Context-Free Languages
L. Prigioniero
2021
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
ciaa-submission.pdf
accesso riservato
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
304.05 kB
Formato
Adobe PDF
|
304.05 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Kutrib-Prigioniero2021_Chapter_BooleanKernelsOfContext-FreeLa.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
296.12 kB
Formato
Adobe PDF
|
296.12 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.