<div class="csl-bib-body">
<div class="csl-entry">Wolfsteiner, S. P. (2020). <i>Grammatical complexity of finite languages</i> [Dissertation, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2020.80501</div>
</div>
-
dc.identifier.uri
https://doi.org/10.34726/hss.2020.80501
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/15037
-
dc.description.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.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Formal Language Theory
en
dc.subject
Context-Free Grammars
en
dc.subject
Grammatical Complexity
en
dc.subject
Descriptional Complexity
en
dc.subject
Computational Complexity
en
dc.subject
Inapproximability
en
dc.subject
Finite Languages
en
dc.subject
Language Operations
en
dc.title
Grammatical complexity of finite languages
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.identifier.doi
10.34726/hss.2020.80501
-
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Simon Peter Wolfsteiner
-
dc.publisher.place
Wien
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
tuw.publication.orgunit
E180 - Fakultät für Informatik
-
dc.type.qualificationlevel
Doctoral
-
dc.identifier.libraryid
AC15687859
-
dc.description.numberOfPages
191
-
dc.thesistype
Dissertation
de
dc.thesistype
Dissertation
en
tuw.author.orcid
0000-0003-0459-8487
-
dc.rights.identifier
In Copyright
en
dc.rights.identifier
Urheberrechtsschutz
de
tuw.advisor.staffStatus
staff
-
tuw.advisor.orcid
0000-0002-6461-5982
-
item.languageiso639-1
en
-
item.fulltext
with Fulltext
-
item.openaccessfulltext
Open Access
-
item.mimetype
application/pdf
-
item.openairetype
doctoral thesis
-
item.grantfulltext
open
-
item.openairecristype
http://purl.org/coar/resource_type/c_db06
-
item.cerifentitytype
Publications
-
crisitem.author.dept
E104-02 - Forschungsbereich Computational Logic
-
crisitem.author.parentorg
E104 - Institut für Diskrete Mathematik und Geometrie