| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| talks:seminar [2019/11/07 23:38] – krivka | talks:seminar [2022/12/01 23:38] (current) – krivka |
|---|
| ===== Program semináře ===== | ===== Program semináře ===== |
| |
| | ==== 2022 ==== |
| | * **5. - 15. 12. 2022: [[http://www.fit.vutbr.cz/~meduna/work/doku.php?id=lectures:lta:lta22|LANGUAGE THEORY with APPLICATIONS 2022]] (LTA 2022) - studentský workshop** |
| | * Podrobný program - [[http://www.fit.vutbr.cz/~meduna/work/doku.php?id=lectures:lta:lta22#conference_schedule|zde]] (přednášky vedeny v angličtině) |
| | * **5. 12. 2022, 11:00 - 13:20, A112, FIT VUT v Brně** |
| | * **[[itomko@fit.vut.cz|Ing. Martin Tomko]]: Multi-Island Finite Automata and Their Even Computation** |
| | * **[[kocman@fit.vut.cz|Ing. Radim Kocman, PhD.]]: Advanced LL parsing techniques** |
| | * Abstrakty a detaily rozvrhu přednášek dostupné na stránce [[:lectures:lta:lta22|LTA 2022]]. |
| | |
| | |
| | ==== 2020 ==== |
| | * **10. - 15. 12. 2020: [[http://www.fit.vutbr.cz/~meduna/work/doku.php?id=lectures:lta:lta20|LANGUAGE THEORY with APPLICATIONS 2020]] (LTA 2020) - studentský workshop (on-line)** |
| | * Podrobný program - [[http://www.fit.vutbr.cz/~meduna/work/doku.php?id=lectures:lta:lta20#conference_schedule|zde]] (přednášky vedeny v angličtině) |
| | * **10. 12. 2020, 12:00 - 13:30, [[https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZjEzZmE4MjgtZDExNi00NjUxLWIxMGMtMzlkODcwNTY0NTIw%40thread.v2/0?context=%7b%22Tid%22%3a%22c63ce729-ca17-4e52-aa2d-96b79489a542%22%2c%22Oid%22%3a%22b0c92057-f3f8-43f5-995e-a5cec0b35bfe%22%7d|On-line přes MS Teams]], FIT VUT v Brně** |
| | * **[[pmartinek@utb.cz|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. |
| |
| ==== 2019 ==== | ==== 2019 ==== |
| |
| * **18. 11. 2019, 15:00 - 16:00, [[http://www.fit.vutbr.cz/FIT/map/fit2.php?show=G202|přednášková místnost G202]], FIT VUT, Božetěchova 2, Brno** | * **18. 11. 2019, 15:00 - 16:00, [[http://www.fit.vutbr.cz/FIT/map/fit2.php?show=G202|přednášková místnost G202]], FIT VUT, Božetěchova 2, Brno** |
| * **[[TODO|Lakshmanan Kuppusamy]]: Descriptional Complexity of Some Regulated Rewriting Grammars** | * **[[lakshma@vit.ac.in|Lakshmanan Kuppusamy]]: Descriptional Complexity of Some Regulated Rewriting Grammars** |
| * **Abstract**: TBA. | * **Abstract**: |
| * **25. 11. 2019, 15:00 - 16:00, [[http://www.fit.vutbr.cz/FIT/map/fit2.php?show=G202|přednášková místnost G202]], FIT VUT, Božetěchova 2, Brno** | * 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. |
| * **[[TODO|Lakshmanan Kuppusamy]]: Descriptional Complexity of Matrix and Graph-Controlled Insertion-Deletion Systems** | * 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. |
| * **Abstract**: TBA. | * **2. 12. 2019, 11:00 - 12:30, [[http://www.fit.vutbr.cz/FIT/map/fit1.php?show=A112|přednášková místnost A112]], FIT VUT, Božetěchova 2, Brno** |
| | * **[[lakshma@vit.ac.in|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, [[http://www.fit.vutbr.cz/FIT/map/fit1.php?show=E112|E112]], FIT VUT, Božetěchova 2, Brno** | * **18. 12. 2019, 11:00 - 12:00, [[http://www.fit.vutbr.cz/FIT/map/fit1.php?show=E112|E112]], FIT VUT, Božetěchova 2, Brno** |
| * **[[ikocman@fit.vutbr.cz|Radim Kocman]]: Jumping Watson-Crick Finite Automata** | * **[[ikocman@fit.vutbr.cz|Radim Kocman]]: Jumping Watson-Crick Finite Automata** |
| * **Abstract**: TBA | * **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. |
| |
| ==== 2018 ==== | ==== 2018 ==== |
