FIT Božetěchova 2, lecture room A113, 11:00-13:00, 29.3.2011
The seminar is organized by the Formal Model Research Group at the Department of Information Systems, Faculty of Information Technology, Brno University of Technology. As its central scientific topic, it discusses formal models and their applications. Recent presentations are to be found at http://www.fit.vutbr.cz/~meduna/work/doku.php?id=talks:seminar.
Author: Géza Horváth (University of Debrecen, Hungary)
Title: Pumping lemmas for linear and nonlinear context-free languages
Abstract: Iteration lemmas are created to prove that given languages do not belong to certain language classes. There are several known pumping lemmas for the whole class and some special classes of the context-free languages. In this talk we recall some old and present some new, interesting pumping lemmas for special linear and context-free language classes. Some of them can be used to pump regular languages in two place simultaneously. Other lemma can be used to pump context-free languages in arbitrary many places.
Author: J. Falucskai (College of Nyíregyháza, Hungary)
Title: Some Algorithms Concerning Uniquely Decipherable Codes
Abstract: The following problem plays an important role in code theory and its applications: Having a set of codewords we have to decide whether there are two or more sequences of codewords which form the same chain of characters of codewords. The problem can be approached in various ways, so the algorithms concerning uniquely decipherable codes use different devices for testing this property. The algorithm of Sardinas--Patterson is based on sequences of sets, other algorithms solve this problem by using finite automata. We present our algorithm, which is based on FA-s.