Title: Grammatical complexity of finite languages
Language: English
Authors: Wolfsteiner, Simon Peter 
Qualification level: Doctoral
Advisor: Hetzl, Stefan 
Issue Date: 2020
Number of Pages: 191
Qualification level: Doctoral
In this thesis, we will investigate finite languages which are generated by different types of context-free grammars from the points of view of descriptional and computational complexity. Specifically, we will study several aspects of the exact and cover complexity of finite languages, i.e., the minimal number of productions a grammar needs in order to generate and cover, respectively, a given finite language. From the point of view of computational complexity, we will consider the following variants of the smallest grammar problem: what is the size or number of productions of a minimal grammar that generates a given finite language? It will be shown that both the minimal size and the minimal number of productions needed in order to generate a given finite language cannot be approximated within certain factors, unless P = NP. In addition, we will also consider problems under the assumption of the so-called Exponential Time Hypothesis. Moreover, from a mere descriptional complexity point of view, we will investigate the exact and cover complexity of different language operations on finite languages. Finally, we will give a relative succinctness classification of several grammar as well as several complexity measure types based on the number of productions.
Keywords: Formal Language Theory; Context-Free Grammars; Grammatical Complexity; Descriptional Complexity; Computational Complexity; Inapproximability; Finite Languages; Language Operations
URI: https://doi.org/10.34726/hss.2020.80501
DOI: 10.34726/hss.2020.80501
Library ID: AC15687859
Organisation: E180 - Fakultät für Informatik 
Publication Type: Thesis
Appears in Collections:Thesis

Files in this item:

Page view(s)

checked on Jul 29, 2021


checked on Jul 29, 2021

Google ScholarTM


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.