Seminář o formálních jazycích a automatech

Tato stránka obsahuje informace o semináři výzkumné skupiny formálních modelů a je průběžně aktualizována.

Od roku 2012 probíhají semináře nepravidelně. Chcete-li být informování o chystaném semináři emailem, dejte vedět. Plnohodnotné semináře budou pořádány pod záštitou ústavních seminářů UIFS. Délka semináře bývá asi jednu hodinu.

• 5. - 15. 12. 2022: LANGUAGE THEORY with APPLICATIONS 2022 (LTA 2022) - studentský workshop
  • Podrobný program - zde (přednášky vedeny v angličtině)
  • 5. 12. 2022, 11:00 - 13:20, A112, FIT VUT v Brně
    • Ing. Martin Tomko: Multi-Island Finite Automata and Their Even Computation
    • Ing. Radim Kocman, PhD.: Advanced LL parsing techniques
      • Abstrakty a detaily rozvrhu přednášek dostupné na stránce LTA 2022.

• 10. - 15. 12. 2020: LANGUAGE THEORY with APPLICATIONS 2020 (LTA 2020) - studentský workshop (on-line)
  • Podrobný program - zde (přednášky vedeny v angličtině)
  • 10. 12. 2020, 12:00 - 13:30, On-line přes MS Teams, FIT VUT v Brně
    • dr. Pavel Martinek: Multiset Languages and Minimization Problem for Multiset Finite Automata
      • Abstract:
        • Multisets (also called bags) represent such a generalization of sets which allow multiplied occurrence of their elements. Finite automata working over multisets differ from usual finite automata in the way how they process their input. Namely, at each computational step, they read a symbol from their input multiset regardless of any ordering of the input. Thus, instead of processing strings of symbols the automata process multisets of symbols. This formalism was already used in defining computational models inspired from biochemistry (like the chemical abstract machine by Berry and Boudol, 1992) or biology (cf. well-known P systems). It has also strong connections to jumping automata introduced by Meduna and Zemek in 2012.
        • The aim of the talk is to describe the concept of multiset automata and their place in formal languages theory, to show their similarities and dissimilarities with classical and jumping finite automata and to deal with minimization of these automata.

• 9. - 18. 12. 2019: LANGUAGE THEORY with APPLICATIONS 2019 (LTA 2019) - studentská konference
  • Podrobný program - zde (přednášky vedeny v angličtině)

• 18. 11. 2019, 15:00 - 16:00, přednášková místnost G202, FIT VUT, Božetěchova 2, Brno
  • Lakshmanan Kuppusamy: Descriptional Complexity of Some Regulated Rewriting Grammars
    • 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 make the grammar to simulate a type-0 grammar. Several regulations are associated with these grammars and are called regulated rewriting grammars. Some of them are (i) Matrix rewriting grammars (ii) Graph-Controlled grammars (iii) Semi-Conditional grammars. The 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.
• 2. 12. 2019, 11:00 - 12:30, přednášková místnost A112, FIT VUT, Božetěchova 2, Brno
  • Lakshmanan Kuppusamy: Descriptional Complexity of Matrix and Graph-Controlled Insertion-Deletion Systems
    • Abstract:
      • Lila Kari introduced the Insertion-deletion system (abbreviated as ins-del system) in formal language theory. Informally, the insertion and deletion operations are defined as follows: if a string w is inserted between two parts u and v of a string uv to get uwv, then we call the operation insertion, whereas if a substring x is deleted from a string uxv to get uv, then we call the operation deletion. Suffixes of u and prefixes of v are called left and right context, respectively. An ins-del system is well described by its size, denoted by (n, i′, i′′; m, j′, j′′) where the parameters from left to right denote (i) the maximal length of the insertion string, (ii) the maximal length of the left context in insertion rules, (iii) the maximal length of the right context used in insertion rules, (iv)-(vi) denote the similar things in deletion rules.
      • Computational completeness for ins-del systems can even be achieved with rule size (1,1,1; 1,1,1) but with no rule size strictly smaller than this. This fact has motivated to study ins-del systems in combination with regulation mechanisms and to achieve the computational completeness with smaller/trade-off size than (1,1,1; 1,1,1). Some of the important variants of ins-del systems are graph-controlled ins-del (GCID) systems, matrix ins-del (MID) system. In matrix ins-del system, the rules are in the form of a matrix and a matrix is a set of ins-del rules. During the derivation, if a matrix is chosen, then all the rules of the matrix are applied in sequentially and in order to the derived string. In graph-controlled ins-del system, there are several components and each component has a set of rules. A transition is performed on the string based on any applicable rule in the current component and the resultant string is moved to the target component specified in the rule itself.
      • In this talk, we see some computational completeness results of matrix and graph-controlled ins-del systems, reducing the ID size, say, to (1,1,0,1,1,0) at the expense of increasing other measures of descriptional complexity. If time permits, we will also see representation of linear languages using these systems with their descriptional complexity measure sizes.

• 18. 12. 2019, 11:00 - 12:00, E112, FIT VUT, Božetěchova 2, Brno
  • Radim Kocman: Jumping Watson-Crick Finite Automata
    • Abstract:
      • In formal language theory, when we study new models, we often want to know whether a certain language can be defined by the model in question. To show that it is possible, we can simply construct an appropriate instance of such a model. However, to show that it is not possible, we have to rigorously prove that no such an instance can exist. If we want to show that a language cannot be defined by the given model and we work with finite or context-free languages, we can use pumping lemmas which are specifically constructed for this task.
      • Nonetheless, when we work with jumping models, it is usually not possible to easily derive such a lemma. Luckily for us, we can usually exploit the fact that jumping models cannot sufficiently control the order of symbols and show that if the model defines some word in the language it also has to define some word that is not in the language. However, in the newly introduced jumping 5'→3' Watson-Crick finite automata this previous approach can no longer be effectively used since the model can easily keep the precise order of symbols for all linear languages.
      • In this talk, we introduce a new concept of the debt of the configuration of the automaton and show how it can be used to prove that a language cannot be defined by the given jumping model.

• 3. - 13. 12. 2018: LANGUAGE THEORY with APPLICATIONS 2018 (LTA 2018) - studentská konference
  • 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 introduces a combined model of jumping finite automata and sensing 5'→3' Watson-Crick finite automata. We will compare the accepting power of the new model with the original models and also with some well-known language families. We will also discuss changes in the accepting power when various restrictions are applied on the model.

• 12. 12. 2018, 11:00 - 12:50, přednášková místnost E112, FIT VUT, Božetěchova 2, Brno
  • Alexander Meduna and Zbyněk Křivka: Jumping Pure Grammars
    • 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.

• 4. - 14. 12. 2017: LANGUAGE THEORY with APPLICATIONS 2017 (LTA 2017) - studentská konference
  • 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

• 5. - 6. 10. 2017, FIT VUT, Božetěchova 2, Brno
  • Thursday, October 5, 2017, 8:00-11:00, room G202: Dr. László Szabó: Stable Marriage Problems I
  • Friday, October 6, 2017, 10:00-12:00, room A112: Dr. László Szabó: Stable Marriage Problems II
    • Abstract: Matching problems arise in numerous applications. Dating services want to pair up compatible couples. Students need to be matched to universities. Other assignment problems involving resource allocation arise frequently, including balancing the traffic load among servers on the Internet. In the following version of the problem suppose we have an equal number of boys and girls. Every boy lists the girls in order of his preference, and every girl lists the boys in order of her preference.
      • We would like to arrange marriages between the boys and girls so that there is not a boy and a girl who prefer one another to their spouses. In their 1962 paper, Gale and Shapely demonstrated that, given a set of preferences for every boy and girl, there is always such a stable matching; even better, they showed how to find one by applying an elegant algorithm. It is relatively straightforward to extend this algorithm to situations where there are an unequal number of boys and girls and we allow polygamous matchings in which parties in one group may be matched with more than one party from the other group, which applies when, e.g., universities accept more than one student.
    • Lecture Notes (PDF, 207 KB)
    • Slides for Lecture I (PDF)
    • Slides for Lecture II (PDF)

• 10. 4. 2017, 13:00 - 14:00, A112, FIT VUT, Božetěchova 2, Brno.
  • Alexandr Meduna: O výslovnosti americké angličtiny
    • 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.
    • Prezentace (zaheslovaný ZIP, 3 MB, máte-li zájem o prezentaci, napište si o heslo)
    • Audio záznam (WMA, 21 MB)

• 5. 12. 2016, 10:00 - 11:00, G202
  • Radim Kocman and Zbyněk Křivka: Jumping Finite Automata: New Results
    • Abstract: PDF
    • Presentation: Part One: Solved Questions and Part Two: New Models

• 5. - 14. 12. 2016: LANGUAGE THEORY with APPLICATIONS 2016 (LTA 2016) - studentská konference
  • Podrobný program - zde (přednášky vedeny v angličtině)

• 14. 12. 2015, 13:00 - 14:00, A113
  • Erzsébet Csuhaj-Varjú (Department of Algorithms and Their Applications, Faculty of Informatics, Eötvös Loránd University, Budapest, Hungary): P automata: an unconventional approach to automata theory
    • Abstract
    • There will be additional discussion and consultations after the talk (14:00 - 16:00 in room A113)

• 7. - 17. 12. 2015: LANGUAGE THEORY with APPLICATIONS 2015 (LTA 2015) - studentská konference
  • Podrobný program - zde (přednášky vedeny v angličtině)

• 15. 6. 2015, 13:00 - 14:30, G108
  • Christian MAUDUIT (Institut de Mathématiques de Luminy, Aix-Marseille University, France): Finite automata and number theory
    • Abstract: The difficulty of the transition from the representation of an integer in a number system (e.g. n = 19605131) to its multiplicative representation (e.g. n = 7.13.17.19.23.29) is at the origin of many important open problems in mathematics and in computer science.
      • The aim of this talk is to give a survey on recent results concerning the combinatorial, arithmetical and statistical properties of sequences of symbols and sequences of integers generated by finite automata, showing deep connections between number theory, combinatorics, computer science and dynamical systems.
      • We will illustrate our talk with some classical examples, including the Thue-Morse sequence, the Rudin-Shapiro sequence and the Cantor sequence.
    • Presentation (PDF, 156 KB)
    • Audio recording (WMA, 25 MB)

• 31. 3. 2015, 13:00 - 14:30, C228
  • Z. Křivka: Skákající gramatiky (Jumping Grammars)
    • Abstrakt: V přibližně hodinovém referátu představím tzv. skákající gramatiky (Jumping Grammars), které reprezentují generativní protějšek ke skákajícím automatům, které byly nedávno zavedeny (Meduna, Zemek 2012). Referát bude vycházet z článku, který s prof. Medunou aktuálně dokončujeme. Ve výkladu budu demonstrovat nové výsledky ohledně generativní síly skákajících gramatik. Porovnám sílu skákajících automatů a gramatik. Skákající gramatiky se pokusím porovnat s klasickými gramatikami. Budeme studovat různé varianty kontextových i bezkontextových skákajících gramatik. Nakonec prostudujeme seminilinearitu jazyků generovaných skákajícími gramatikami a nastíníme další výzkum v oblasti skákajících gramatik.
    • Prezentace (PDF, 697 KB)
    • Audio záznam (WMA, 89,3 MB)

• 9. - 18. 12. 2014: LANGUAGE THEORY with APPLICATIONS 2014 (LTA 2014) - studentská konference
  • Podrobný program - zde (přednášky vedeny v angličtině)

• 9. 12. 2014, 14:00-15:00, room D2, FI MUNI, Botanická 68a, Brno
  • A. Meduna: Regulated Grammars and Automata

• 27. 3. 2014, 14:00 - 15:00, C228
  • Z. Křivka: Picture Languages and Pure Two-dimensional Context-free Grammars
    • Abstract: Na hodinovém semináři bych rád provedl stručný přehled obrázkových jazyků (Picture Languages) a jejich různých variant. Druhou část semináře bych rád věnoval prezentaci výsledků zaslaných na mezinárodní konferenci IWCIA 2014 o speciálním typu čistých 2D gramatik generujících obrázkové jazyky.
    • Prezentace (PDF, 500 KB)

• 3. 2. 2014, 13:00 - 14:00, A112
  • R. Tesař: Alan Mathison Turing - přednáška o jeho životě a díle
    • Abstract: V přibližně hodinovém referátu se dozvíte mnoho o životě a díle této velevýznamné osobnosti informatiky. Přednáška bude logicky členěna do několik částí (období před válkou, během druhé světové války, Riemannova hypotéza a funkce Zeta, poválečné období a význam Alana Turinga v současnosti). Podrobnější abstrakt v PDF.
    • Prezentace (PDF, 1,5 MB)
    • Videozáznam (AVI, 410 MB)

• 11. - 12., 18. - 19. 12. 2012: LANGUAGE THEORY with APPLICATIONS 2013 (LTA 2013) - studentská konference
  • Podrobný program - zde (přednášky vedeny v angličtině)

• 12. 12. 2012, 09:00, G202
  • A. Meduna, P. Zemek: Regulated Grammars and Automata
    • Abstract

• 9. 4. 2013, 10:00 - 11:30, A112
  • Dr. José Ignacio Farrán Martín (Universidad de Valladolid (Campus de Segovia), Spain): CRYPTOLOGY AND COMPUTER SECURITY
    • Abstract:
      • The talk will be an overview of Cryptology, that is Cryptography plus Cryptanalysis, including a historical perspective and some practical applications. The talk will be specially focused on the mathematical ideas underlying the techniques in Cryptology.
    • Presentation (PDF)

• 10. - 13. 12. 2012: LANGUAGE THEORY with APPLICATIONS 2012 (LTA 2012) - studentská konference
  • Podrobný program - zde (přednášky vedeny v angličtině)

• 10. 12. 2012, 12:30, G202
  • A. Meduna, P. Zemek: Jumping Finite Automata
    • Abstract

• 13. - 15. 12. 2011: LANGUAGE THEORY with APPLICATIONS 2011 (LTA 2011) - studentská konference
  • Podrobný program - zde
• 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.
  • Obě přednášky uskutečněny v rámci projektu MŠMT MEB041003.
• 21. 7. 2011, 10:00 - 11:00, C228
  • János Falucskai (College of Nyíregyháza, Hungary): A New Interpretation of the Decipherability
    • Abstract
  • Přednáška uskutečněna v rámci projektu MŠMT MEB041003.
• 7. 7. 2011, 10:00 - 11:00, C228
  • P. Dömösi (College of Nyíregyháza, Hungary): Context-free languages and primitive words
    • Abstract
  • Přednáška uskutečněna v rámci projektu MŠMT MEB041003.
• 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.
  • Obě přednášky uskutečněny v rámci projektu MŠMT MEB041003.
• 23. 3. 2011, 10:00, C228
  • P. Zemek: O (rozšířených) Szilardových jazycích
    • Abstrakt: Ke každému pravidlu gramatiky přiřadíme unikátní návěští, které jej označuje. Szilardův jazyk je pak definován jako množina všech posloupností návěští pravidel použitých v úspěšné derivaci v dané gramatice. Pokud navíc tyto posloupnosti připojíme za generované řetězce, dostaneme tzv. rozšířený Szilardův jazyk. Prezentace bude rozdělena na dvě části. V první části budou posluchači seznámeni s konceptem (rozšířených) Szilardových jazyků a budou shrnuty základní poznatky. V druhé části pak budou prezentovány vlastní, nové výsledky týkající se generovaní těchto jazyků bezkontextovými gramatikami řízenými regulárním jazykem.
• 16. 3. 2011, 10:00, C228
  • J. Křoustek, S. Židek: Využití gramatik s rozptýleným kontextem pro modelování omezení instrukcí VLIW procesorů
    • Abstrakt: V této prezentaci bude představena nová metoda pro generování kódu pro procesory s dlouhým instrukčním slovem (VLIW), která je založena na využití gramatik s rozptýleným kontextem. Oproti stávajícím metodám je efektivnější díky kontrole konfliktů již během generování kódu. Dále bude prezentována optimalizace této metody pomocí nově navrženého formálního modelu - gramatik s rozptýleným kontextem s prioritními pravidly. Na závěr bude prezentován důkaz generativní síly těchto gramatik. Prezentace je souhrnem publikační činnosti obou autorů na toto téma.
• 9. 3. 2011, 10:00, C228
  • P. Horáček: Syntaxí řízený japonsko-český překlad (disertační teze)
    • Abstrakt: Příspěvek je věnován možnostem automatizovaného překladu mezi japonštinou a češtinou. Především se zabývá formálními nástroji, které lze pro tento úkol využít. Navrhovaný způsob je založen na syntaktické analýze a formálním popisu japonské větné struktury. První část tezí obsahuje úvod do problematiky a stručný přehled současného stavu poznání v oblasti. Následuje stanovení cílů disertační práce, návrh metod k jejich dosažení a prezentace dosavadních výsledků. Závěr shrnuje konkrétní cíle práce a možnosti dalšího výzkumu a vývoje.
• 2. 3. 2011, 10:00, C228
  • L. Vrábel, P. Zemek: O nedeterminismu v programovaných gramatikách
    • Abstrakt: V této prezentaci je diskutován vliv nedeterminismu na generativní sílu programovaných gramatik. Pod nedeterminismem rozumíme situaci, kdy po aplikaci pravidla je v následujícím kroku možno aplikovat více než jedno pravidlo. Zaměříme se jak na redukci maximálního počtu nedeterministických voleb na jedno pravidlo, tak na redukci celkového součtu těchto voleb v gramatice. Prezentace je založena na našem příspěvku zaslaném na AFL'11.
• 16. 2. 2011, 11:00, C228
  • F. Goldefus, O. Jirák: SLD rezoluce a lambda kalkul
    • Abstrakt: V této prezentaci bude nejprve probrána základní problematika SLD rezoluce a lambda kalkulu. Tyto formalismy jsou základem pro logické a funkcionální programovací jazyky. Pomocí SLD rezoluce se dokazuje nesplnitelnost cíle (negace predikátu). Lambda kalkul vyjádřuje a vyčísluje rekurzivně spočetné funkce. Na závěr budou předvedeny vizualizace vybraných příkladů lambda kalkulu a SLD rezoluce s využitím animace v Adobe Flash, která je součástí FRVŠ projektu.

• 24. 11., 1. 12., 8. 12., 15. 12. 2010, 9:00 - 12:00, C228
  • Dílna moderní teoretické informatiky
• 3. 11. 2010, 12:15, A112
  • P. Horáček: Syntaxí řízený japonsko-český překlad
    • Abstrakt: Syntaxí řízený překlad je dobře prozkoumanou oblastí teorie formálních jazyků s významnými aplikacemi např. v překladačích programovacích jazyků. V příspěvku se snažíme aplikovat jej také na přirozené jazyky. Budou uvedeny potřebné definice a navrženo rozšíření s využitím maticových gramatik. Následovat bude několik praktických příkladů překladu japonských vět na české.
• 20. 10. 2010, 12:15, A112
  • O. Jirák: Modelování a tvorba editoru pomocí GMF pro Eclipse
    • Abstrakt: Využití Graphical Modeling Framework (GMF) při tvorbě modelů - definice modelu (podpůrné nástroje - Emfatic), úpravy (struktura projektu, modifikace a přidávání funkcionality), programový přístup k modelu (vytvoření, načtení, modifikace). Následovat bude popis tvorby editoru pro tento model. Na závěr budou probrány pokročilejší úpravy editoru (tvorba vlastních “custom figures”). Vše doplněno názornými ukázkami.
• 28. 4. 2010, 11:00, C228
  • P. Petřík: Parallel Finite Automata Systems Communicating by Transitions
    • Abstract: Various types of grammar systems were investigated in the formal language theory. These systems consist of various types of cooperating grammars and generate the language. Moreover, there are works focused on the systems with a different approach to the generation of the language (Multigenerative GS). On the other hand, there is no work dealing with the systems based on different types of automata. The works investigating automata systems already exist, but the area of automata systems is not so comprehensive like the area of grammar systems. In this work, we focus on the theory of parallel (communicating) automata systems with finite state machines as its components. We define these systems and focus primarily on proof constructions considering already known grammar systems or other grammar structures like matrix grammars.
• 14. 4. 2010, 11:00, C228
  • J. Koutný: On n-Path-Controlled Grammars
    • Abstract: The topic deals with context-free grammars with some root-to-leaf paths in derivation trees restricted by control languages. It demonstrates that if these control languages are linear, then there are several families of generated languages depending on the common part of all restricted paths. The talk discusses the investigation of several properties of these families, especially the pumping lemma for one of these classes.
• 7. 4. 2010, 11:00, C228
  • P. Solár: Obecné k-omezené vymazávání v gramatikách s rozptýleným kontextem
    • Abstrakt: Gramatiky s rozptýleným kontextem (SC) se od běžných bezkontextových gramatik liší především v možnosti přepisovat několik neterminálních symbolů zároveň pomocí aplikace jediného pravidla. Generativní síla obecných SC gramatik (s vymazávacími pravidly) je na úrovni rekurzivně vyčíslitelných jazyků. V případě nevymazávajících (propagating) SC gramatik je ale tato generativní síla výrazně ovlivněna. V příspěvku budou prezentovány možnosti vymazávání neterminálních symbolů. Především z pohledu k-omezeného vymazávání. Bude prezentován postup převodu SC gramatik s vymazávacími pravidly, splňujících uvedenou podmínku, na gramatiky bez vymazávacích pravidel. Příspěvek bude založen na knize Meduna, A., Techet, J.: Scattered Context Grammars, WITPress, 2010.
• 31. 3. 2010, 11:00, C228
  • M. Čermák: Multijazyky, multigramatické systémy a multipřijímající automatové systémy
    • Abstrakt: Čistě teoretický seminář otevře novou problematiku formálních modelů, přičemž se bude v první části prezentace věnovat multijazykům a multigramatickým systémům. V druhé části prezentace budou zavedeny multipřijímající automatové systémy řízené stavem a přechodem. V závěru prezentace bude diskutována přijímající síla zavedených systémů a otevřené problémy multipřijímajících automatových systémů.
• 24. 3. 2010, 11:00, C228
  • Formal Models in Processing of Japanese Language (Petr Horáček)
    • Abstrakt: První část referátu je věnována problematice japonských znaků kanji. Jde zde především o grafické hledisko, tj. možnosti rozpoznávání znaků a zobrazení znaků na základě popisu (návaznost na diplomovou práci). Zmíněna je ale i sémantická stránka (jak reprezentovat různé významy a čtení znaků). Dále se referát zabývá japonskou gramatikou. Snaží se najít prostředky moderní teoretické informatiky, pomocí nichž by bylo možné vhodně modelovat syntax japonštiny. Bližší pozornost je věnována řízeným gramatikám (konkrétně bude prezentován příklad s využítím maticové gramatiky) a zejména pak gramatikám s rozptýleným kontextem. V závěru jsou představeny některé specifické problémy, na které v japonštině narážíme.
• 17. 3. 2010, 11:00, C228
  • Table-Driven Parsing of Scattered Context Grammar (Ota Jirák)
    • Abstract: Existing methods of parsing scattered context grammars somehow expand nonterminals deep in the pushdown, which is time expensive operation. Therefore, this paper presents parsing algorithm of scattered context grammar based on table-driven principles, commonly known for context-free top-down parsing, illustrates its work on a short example and discusses future work. This approach works with only the pushdown top. Intuitively, it should be faster than other techniques.
• 10. 3. 2010, 11:00, C228
  • k-Limited Erasing Performed by Regular-Controlled Context-Free Grammars (P. Zemek)
    • Abstrakt: Bude prezentována podmínka, za které je možné z libovolné gramatiky řízené regulárním jazykem odstranit vymazávací pravidla (bez změny generovaného jazyka; samozřejmě až na generování prázdného řetězce).

• 2.12.2009, 12:00, C228
  • Multigenerativní systémy (E. Zámečníková)
    • Abstrakt: Pojednání o multigenerativních gramatických systémech. Bude uvedeno, na čem jsou tyto multigenerativní systémy založeny, a rozdělení těchto systémů na základě typu derivace, která je provedena. Dále pak zmíním možný další výzkum v této oblasti.
• 25.11.2009, 12:00, C228
  • Scattered Context Grammars for Generating and Reducing Parse Trees (S. Židek)
• 18.11.2009 - VOLNO
• 11.11.2009, 12:00, C228
  • Eclipse Modeling Framework (EMF, GMF) (O. Jirák)
• 4.11.2009, 12:00, C228
  • Homomorphic characterisations of recursively enumerable languages with very small language classes by S. Okawa and S. Hirose (L. Rychnovský)
• 21.10.2009, 12:00, C228
  • Řezy v derivačních stromech (J. Koutný)
• 14.10.2009, 12:00, C228
  • Omezené Turingovy stroje (Z. Křivka)
    • Krátká anotace: Na přednášce si představíme prostorovou složitostí omezené Turingovy stroje a budeme studovat jejich sílu. Představíme několik příkladů s logaritmickou a sublogaritmickou prostorovou složitostí a nakonec si povíme o dolním ohraničení prostorové složitosti, která ještě vede na neregulární jazyky.
• 07.10.2009, 12:00, C228
  • Metody převodu konečných automatů na regulární výrazy (P. Zemek)
• 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
  • O návratech v konečných automatech (A. Meduna)

• Emailová konference pro účely pozvánek, oznámení a organizačních záležitostí semináře
  • fm@fit.vutbr.cz
  • Pokud si přejete být v seznamu odběratelů nebo nebýt v tomto seznam, pište na krivka@fit.vutbr.cz

• privátní sekce - vstup pod heslem pro členy skupiny, v případě zájmu o přístup zašlete email na krivka@fit.vutbr.cz.

• 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.

• DBLP - databáze publikací z Computer Science
• Czech Digital Mathematics Library - např. všechny články časopisu Kybernetika