This is an old revision of the document!
Program semináře
2019
-
Podrobný program -
zde (přednášky vedeny v angličtině)
-
-
Abstract:
It is well known that the set of context-free languages is a strict subset of the set of recursively enumerable languages. Analogously, a type-2(or context-free) grammar cannot simulate a type-0 grammars. However, if we control or regulate the application of the context-free rules, then we can makethe grammar to simulate a type-0 grammar. Several regulations are associated with these grammars and are called regulated rewriting grammars. Some of themare (i) Matrix rewriting grammars (ii) Graph-Controlled grammars (iii) Semi-Conditional grammars. Descriptional complexity investigates the economical measures required for a grammatical device, automaton, or a rewriting system for a succinct representation of a formal language class.
In this talk, we are going to concentrate on semi-conditional grammars and their variants simple semi-conditional and generalized forbidden grammars. In a semi-conditional grammar, the derivations are controlled by permitting string and/or forbidden string that are associated with each rule and is known as conditional rule. The maximum lengths of permitting strings of permitting and forbidden strings refer to the degree of the system. Besides degree, the number of nonterminals and the number of conditional rules are considered to be descriptional complexity measures. We will see the computational completeness results of the above said systems with minimal/succinct sizes of measures. Our proofs include some novel ideas and effective use of Geffert normal forms. In the sequel, we will review some results available in the literature; many of the results are contributed by Prof. Alexander Meduna and his research group.
-
Lakshmanan Kuppusamy: Descriptional Complexity of Matrix and Graph-Controlled Insertion-Deletion Systems
18. 12. 2019, 11:00 - 12:00, E112, FIT VUT, Božetěchova 2, Brno
2018
-
Podrobný program -
zde (přednášky vedeny v angličtině)
6. 12. 2018, 11:00 - 11:30, A112, FIT VUT, Božetěchova 2, Brno
Radim Kocman: A Jumping 5'→3' Watson-Crick Finite Automata Model
-
-
Abstract: This talk will introduce jumping pure grammars, which are conceptualized just like classical pure grammars except that during the applications of their productions, they can jump over symbols in either direction within the rewritten strings. We will compare the generative power of jumping pure grammars with that of classical pure grammars while distinguishing between their versions with and without erasing productions. Apart from sequential versions, we will present an analogical study in terms of parallel versions of jumping pure grammars represented by 0L grammars. During the talk, several open problems will be introduced to suggest the future investigation of jumping pure grammars.
2017
-
Podrobný program -
zde (přednášky vedeny v angličtině)
22. 11. 2017, FIT VUT, Božetěchova 2, Brno
Wednesday, November 22, 2017, 13:00 - 13:50, room
E112:
Dr. Benedek Nagy: Linear context-free languages and Watson-Crick automata
Abstract: Watson-Crick automata are inspired from the Nature, as instead of a normal tape, a Watson-Crick tape, i.e., a DNA molecule is considered as input. A DNA molecule has two strands, subsequently Watson-Crick automata have two reading heads, one for each strand. DNA strands have orientation, the 5'→3' direction is preferred in some biochemical reactions. In 5'→3' Watson-Crick automata the two reading heads start from the two extremes of the input (the opposite ends of the molecule) and finish the process when the heads meet. With 5'→3' Watson-Crick finite automata the class of linear context-free languages can be accepted, and some of its subclasses by some restricted variants. Deterministic variant characterizes a proper subset of linear languages, the class 2detLIN. This class is incomparable with the traditional detLIN, the class of languages that can be accepted by deterministic 1-turn PDA.
Dr. Nagy is internationally well-known computer scientist (
RG Score above 27) and an associate professor at Department of Mathematics, Faculty of Arts and Sciences, Eastern Mediterranean University, North Cyprus (Turkey).
Presentation: N/A
22. 11. 2017, FIT VUT, Božetěchova 2, Brno
Wednesday, November 22, 2017, 14:00 - 15:00, seminar room
C228:
Dr. Benedek Nagy: On 5' → 3' Watson-Crick finite and pushdown automata
Abstract: In 5'→3' Watson-Crick automata the two reading heads start from the two extremes of the input (the opposite ends of the molecule) and finish the process when the heads meet. With 5'→3' Watson-Crick finite automata the class of linear context-free languages can be accepted, and some of its subclasses by some restricted variants. Extending these automata with a pushdown stack, a new mildly context-sensitive family of languages can be accepted containing all the context-free languages, and the linguistically important three non-context-free languages. Variants of this model will also be shown.
Presentation: N/A
10. 4. 2017, 13:00 - 14:00,
A112, FIT VUT, Božetěchova 2, Brno.
-
Anotace: Výslovnost americké angličtiny obsahuje některé zvuky, které Čech imituje chybně. Učitelé, včetně rodilých mluvčích, tyto odchylky zpravidla tolerují a spokojí se s touto nesprávně provedenou imitací, pokud je alespoň trochu srozumitelná. Prezentovaná přednáška naopak na tyto zvuky explicitně upozorní a načrtne, jak je vysloví Američan. Prezentace bude mít neformální charakter.
-
-
2016
5. 12. 2016, 10:00 - 11:00,
G202
-
Podrobný program -
zde (přednášky vedeny v angličtině)
2015
14. 12. 2015, 13:00 - 14:00,
A113
-
Podrobný program -
zde (přednášky vedeny v angličtině)
15. 6. 2015, 13:00 - 14:30,
G108
2014
-
Podrobný program -
zde (přednášky vedeny v angličtině)
9. 12. 2014, 14:00-15:00, room D2, FI MUNI, Botanická 68a, Brno
2013
-
Podrobný program -
zde (přednášky vedeny v angličtině)
2012
-
Podrobný program -
zde (přednášky vedeny v angličtině)
2011
-
2. 11. 2011, 12:00 - 13:00, C228
P. Dömösi (College of Nyíregyháza, Hungary): Something About Cryptography
Abstract: Symmetric and asymetric cryptosystems are considered including Polybius cryptosystem, Caesar code, Richelieu cryptosystem, Enigma, Purple, Navajo code, DES, RSA, Pretty Good Pryvacy. In addition a novel symmetric cryptosystem is shown.
G. Horváth (University of Debrecen, Hungary): The Language of Primitive Words
Abstract: A nonempty word is said to be primitive if it is not a proper power of another word. A number of papers investigated the language of all primitive words over an alphabet with more than one letter, concerning its relation to the Chomsky hierarchy. In [1] the authors conjectured that this language is not context-free. This twenty years old conjecture is still open. In this talk I will present recent results and our ongoing research on this topic.
-
21. 7. 2011, 10:00 - 11:00, C228
János Falucskai (College of Nyíregyháza, Hungary): A New Interpretation of the Decipherability
-
7. 7. 2011, 10:00 - 11:00, C228
P. Dömösi (College of Nyíregyháza, Hungary): Context-free languages and primitive words
-
29. 3. 2011, 11:00 - 13:00, A113
J. Falucskai (College of Nyíregyháza, Hungary): 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.
G. Horváth (University of Debrecen, Hungary): 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.
-
23. 3. 2011, 10:00, C228
16. 3. 2011, 10:00, C228
9. 3. 2011, 10:00, C228
2. 3. 2011, 10:00, C228
16. 2. 2011, 11:00, C228
2010
24. 11., 1. 12., 8. 12., 15. 12. 2010, 9:00 - 12:00, C228
3. 11. 2010, 12:15, A112
20. 10. 2010, 12:15, A112
28. 4. 2010, 11:00, C228
14. 4. 2010, 11:00, C228
7. 4. 2010, 11:00, C228
31. 3. 2010, 11:00, C228
24. 3. 2010, 11:00, C228
17. 3. 2010, 11:00, C228
10. 3. 2010, 11:00, C228
2009
2.12.2009, 12:00, C228
25.11.2009, 12:00, C228
18.11.2009 - VOLNO
11.11.2009, 12:00, C228
4.11.2009, 12:00, C228
21.10.2009, 12:00, C228
14.10.2009, 12:00, C228
07.10.2009, 12:00, C228
23.09.2009, 12:00, C228
Regulovaný nedeterminismus v zásobníkových automatech (T. Masopust)
Základní informace o hledání literatury ve formálních jazycích (Z. Křivka, cca 10 minut)
20.05.2009, 12:00, C228
Privátní sekce
Historie
Seminář v zimním semestru akademického roku 2011/2012 probíhal nepravidelně ve
středu od
12:00 v místnosti
C228.
Seminář v letním semestru akademického roku 2010/2011 probíhal ve
středu od
10:00 v místnosti
C228.
Seminář v zimním semestru akademického roku 2010/2011 probíhal ve
středu od
12:15 v místnosti
A112.
Seminář v letním semestru akademického roku 2009/2010 probíhal ve
středu od
11:00 v místnosti
C228. Plnohodnotné semináře jsou nově pořádány pod záštitou
ústavních seminářů UIFS.
Zajímavé odkazy
DBLP - databáze publikací z Computer Science
-