Paradygmaty Języków Programowania

dr Grzegorz Herman

środa 14:15-16:00, sala 0174

Poprzednie referaty

10.06.2020 12:15
Wojciech Grabis
Decidability of regular language genus computation by Guillaume Bonfante and Florian L. Deloup
This article continues the study of the genus of regular languages that the authors introduced in a 2013 paper (published in 2018). In order to understand further the genus g(L) of a regular language L, we introduce the genus size of |L|_gen to be the minimal size of all finite deterministic automata of genus g(L) computing L. We show that the minimal finite deterministic automaton of a regular language can be arbitrarily far away from a finite deterministic automaton realizing the minimal genus and computing the same language, in terms of both the difference of genera and the difference in size. In particular, we show that the genus size |L|_gen can grow at least exponentially in size |L|. We conjecture, however, the genus of every regular language to be computable. This conjecture implies in particular that the planarity of a regular language is decidable, a question asked in 1976 by R. V. Book and A. K. Chandra. We prove here the conjecture for a fairly generic class of regular languages having no short cycles. The methods developed for the proof are used to produce new genus-based hierarchies of regular languages and in particular, we show a new family of regular languages on a two-letter alphabet having arbitrary high genus.
10.06.2020 12:15
Wojciech Grabis
Decidability of regular language genus computation by Guillaume Bonfante and Florian L. Deloup
This article continues the study of the genus of regular languages that the authors introduced in a 2013
paper (published in 2018). In order to understand further the genus g(L) of a regular language L, we
introduce the genus size of |L|gen to be the minimal size of all finite deterministic automata of genus g(L)
computing L.We show that the minimal finite deterministic automaton of a regular language can be arbitrarily
far away from a finite deterministic automaton realizing the minimal genus and computing the
same language, in terms of both the difference of genera and the difference in size. In particular, we show
that the genus size |L|gen can grow at least exponentially in size |L|. We conjecture, however, the genus of
every regular language to be computable. This conjecture implies in particular that the planarity of a regular
language is decidable, a question asked in 1976 by R. V. Book and A. K. Chandra. We prove here the
conjecture for a fairly generic class of regular languages having no short cycles. The methods developed
for the proof are used to produce new genus-based hierarchies of regular languages and in particular, we
show a new family of regular languages on a two-letter alphabet having arbitrary high genus.
10.06.2020 12:15
Wojciech Grabis
Decidability of regular language genus computation by Guillaume Bonfante and Florian L. Deloup
This article continues the study of the genus of regular languages that the authors introduced in a 2013 paper (published in 2018). In order to understand further the genus g(L) of a regular language L, we introduce the genus size of |L|gen to be the minimal size of all finite deterministic automata of genus g(L) computing L.We show that the minimal finite deterministic automaton of a regular language can be arbitrarily far away from a finite deterministic automaton realizing the minimal genus and computing the same language, in terms of both the difference of genera and the difference in size. In particular, we show that the genus size |L|gen can grow at least exponentially in size |L|. We conjecture, however, the genus of every regular language to be computable. This conjecture implies in particular that the planarity of a regular language is decidable, a question asked in 1976 by R. V. Book and A. K. Chandra. We prove here the conjecture for a fairly generic class of regular languages having no short cycles. The methods developed for the proof are used to produce new genus-based hierarchies of regular languages and in particular, we show a new family of regular languages on a two-letter alphabet having arbitrary high genus.