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.
Settore INF/01 - Informatica
2021
Book Part (author)
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/862331
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact