Title: Grammatical Complexity of Finite Languages
Language: English
Authors: Wolfsteiner, Simon Peter 
Qualification level: Doctoral
Keywords: Formal Language Theory; Context-Free Grammars; Grammatical Complexity; Descriptional Complexity; Computational Complexity; Inapproximability; Finite Languages; Language Operations
Advisor: Hetzl, Stefan 
Issue Date: 2020
Number of Pages: 191
Qualification level: Doctoral
Abstract: 
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.
URI: https://doi.org/10.34726/hss.2020.80501
http://hdl.handle.net/20.500.12708/15037
DOI: 10.34726/hss.2020.80501
Library ID: AC15687859
Organisation: E180 - Fakultät für Informatik 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:

File Description SizeFormat
Grammatical Complexity of Finite Languages.pdf1.3 MBAdobe PDFThumbnail
 View/Open
Show full item record

Page view(s)

68
checked on Mar 1, 2021

Download(s)

137
checked on Mar 1, 2021

Google ScholarTM

Check


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