%0 Conference Proceedings
%T On the Grammatical Complexity of Finite Languages
%+ Justus-Liebig-Universität Gießen = Justus Liebig University (JLU)
%+ Vienna University of Technology = Technische Universität Wien (TU Wien)
%A Holzer, Markus
%A Wolfsteiner, Simon
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 20th International Conference on Descriptional Complexity of Formal Systems (DCFS)
%C Halifax, NS, Canada
%Y Stavros Konstantinidis
%Y Giovanni Pighizzini
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-10952
%P 151-162
%8 2018-07-25
%D 2018
%R 10.1007/978-3-319-94631-3_13
%Z Computer Science [cs]Conference papers
%X We study the grammatical production complexity of finite languages w.r.t. (i) different interpretations of approximation, i.e., equivalence, cover, and scattered cover, and (ii) whether the underlying grammar generates a finite or infinite language. In case the generated language is infinite, the intersection with all words up to a certain length has to be considered in order to obtain the finite language under consideration. In this way, we obtain six different measures for regular, linear context-free, and context-free grammars. We compare these measures according to the taxonomy introduced in [J. Dassow, Gh. Păun: Regulated Rewriting in Formal Language Theory, 1989] with each other by fixing the grammar type and varying the complexity measure and the other way around, that is, by fixing the complexity measure and varying the grammar type. In both of these cases, we develop an almost complete picture, which gives new and interesting insights into the old topic of grammatical production complexity.
%G English
%Z TC 1
%Z WG 1.2
%2 https://inria.hal.science/hal-01905630/document
%2 https://inria.hal.science/hal-01905630/file/470153_1_En_13_Chapter.pdf
%L hal-01905630
%U https://inria.hal.science/hal-01905630
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-WG1-2
%~ IFIP-LNCS-10952