LANGUAGE THEORY with APPLICATIONS 2017 (LTA 2017)

LTA 2017 is 7th student conference at the Faculty of Information Technology, Brno University of Technology.

• Subject: Formal language theory and its applications in computer science
• Place: FIT BUT, Brno, Czech Republic
• Date: November 22, November 27, and December 4 - 14, 2017

• Organizers:
  1. the TID and VYPa teaching teams;
  2. Formal Model Research Group, FIT BUT;
  3. Department of Information Systems, FIT BUT.

• Committee:
  • Alexander Meduna (chair)
  • Zbyněk Křivka
  • Radim Kocman
  • Jakub Martiško
  • Lucie Charvát

• Conference language: English

• Coverage:
  • LTA 2017 offers a variety of scientific talks on formal language theory and its computer-related applications at MSc and PhD levels. A special attention is paid to modern applications related to the language translation. Most of the talks results from the students' work in the TID and VYPa classes taught at FIT BUT.

• Style:
  • Talks are presented so they clearly and quickly explain their significance to today's computer science. As a result, in some instances, results and their proofs may be merely outlined in an informal way. LTA does not tolerate presentations that hide their shallow contents behind exotic pictures.

• Purpose: The purpose of this event is three-fold:
  1. demonstrating the TID and VYPa student work in public;
  2. giving students the opportunity of presenting scientific talks in English;
  3. improving a communication between students and teachers interested in the subject of the conference.

• Audience: Everybody is welcome to attend this event without any prior notice. There is no payment.

• Questions: Contact Zbyněk Křivka

• Acknowledgement: This conference is partially supported by TAČR grant Visual Computing Competence Center (V3C), TE01020415.

• Speaker: dr. Benedek Nagy, Eastern Mediterranean University, North Cyprus (Turkey)
• Title: 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.
• Presentation: For students of FIT, there is a videorecording available (or just screen)
• Level: Bc/MSc
• Date: November 22, 2017, 13:00 - 13:50
• Chair: Alexander Meduna
• Room: E112

• Speaker: dr. Benedek Nagy, Eastern Mediterranean University, North Cyprus (Turkey)
• Title: On 5' → 3' Watson-Crick finite and pushdown 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. 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: NA (in progress)
• Level: PhD
• Date: November 22, 2017, 14:00 - 15:00
• Chair: Zbyněk Křivka
• Room: C228

• Speaker: Alexander Meduna, FIT VUT, Brno
• Title: English: American Pronunciation (in Czech: O výslovnosti americké angličtiny)
• Note: Repeated performance/Pro velký zájem je přednáška opakována.
• Abstract (in Czech): 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.
• Date: November 27, 2017, 11:00 - 12:00
• Room: G202
• Materials: Slides (PDF), public audio-video recording (MP4, 298 MB)

• Speaker: dr. Vladimír Janoušek, FIT VUT v Brně
• Abstract: Tématem přednášky bude Chuck Berry s důrazem na brilantní texty jeho písní. V prezentaci zazní jeho hudba a budou zmíněny i související okolnosti, které se váží ke kořenům a podstatě rock'n'rollu, jehož je Chuck Berry ikonickou postavou.
• Date: November 27, 2017, 12:00 - 13:00
• Room: G202

• Title: Cestou Václava Hraběte
• Date: December 5, 2017, 19:00
• Place: Malé divadlo vína, #vinarium, Starobrněnská 13, Brno
• Reciter: Alexander Meduna
  • guitar accompaniment: Miloš Kalina (guitar and original songs)
  • Czech invitation, Facebook event webpage

The list of talks in VYPa and TID courses follows.

• Classroom: G202
• Chair: Alexander Meduna
• Talk duration: 15 minutes (including discussion)
• Level: MSc
• Talks: Parsing Techniques

• Gabonay Michal, Kocour Martin: Parsing Mixfix Operators (Abstract)
• Chalk Matěj, Pilátová Kateřina: Precedence Climbing (Abstract)
• Hrstka Jan, Riša Martin: Left-Corner Parsing (Abstract)
• Garcia Alvarez Moises: Tabular Parsing (Abstract)

• Černý Jan, Kadlčíková Hana: LL(*) Parsing (Abstract)
• Kožušník Adam, Weisser Filip: (LL) Scattered Context Grammars (Abstract)
• Vít Radek, Ženčák Tomáš: Generating LL Translation Grammars for Arithmetic Expressions (Abstract)
• Hošták Viliam Samuel, Turcel Matej: Controlled Pure Grammar Systems (Abstract)

• Classroom: A113
• Chair: Radim Kocman
• Talk duration: 25 minutes (including discussion)
• Level: PhD
• Talks:

Invited short talk, 11:00-11:30:

• Jakub Martiško: CD Grammar Systems with Two Propagating Scattered Context Components Characterize the Family of Context Sensitive Languages
  • Abstract: The L(PSCG)=L(CS) problem asks whether propagating scattered context grammars and context sensitive grammars are equivalent. The presented paper reformulates and answers this problem in terms of CD grammar systems. More specifically, it characterizes the family of context sensitive languages by two-component CD grammar systems with propagating scattered context rules.

Regular talks, 11:30 - 12:45:

• Kristian Kadlubiak: Automated GPU Kernel Transformation as an Optimization Problem (Abstract, Slides)
• Gabriel Bordovský: Optimal dataset transformations for ultrasound simulation (Abstract, Slides)
• Martin Očenáš: Security analysis of PEAP protocol using NuSMV tool (Abstract, Slides)

• Classroom: G202
• Chair: Zbyněk Křivka
• Talk duration: 15 minutes (including discussion)
• Level: MSc
• Talks: Formalisms, Paradigms, and Code generation

• Caha Petr, Černošek Bedřich: Alternative Finite Automata Minimization (Abstract)
• Beníčková Zuzana, Regéciová Dominika: Extended Versions of Regular Expressions (Abstract)

• Klimaj Daniel, Pokorný Filip: Simple Code Generation (Abstract)
• Rozkopál Kamil, Svoboda Jan: Object-Orientation - Multiple Inheritance (Abstract)
• Bajaník Filip, Haris Daniel: Exception Handling Implementation (Abstract)
• Holcman Jaroslav, Kubiš Jan: JIT Compilation in V8 JS Engine (Abstract)
• Josefík Martin, Malík Pavol: Closures and High-order Functions (Abstract)

• Classroom: A113
• Chair: Jakub Martiško
• Talk duration: 25 minutes (including discussion)
• Level: PhD
• Talks:

Invited short talk, 11:00-11:30:

• Radim Kocman: General CD Grammar Systems and Their Simplification
  • Abstract: This talk introduces general CD grammar systems, whose components are general grammars, so they are computationally complete—that is, they characterize the family of recursively enumerable languages. We investigate them working under the * mode and the t mode. Most importantly, we will present two transformations that turn arbitrary general grammars into equivalent two-component general CD grammar systems with a context-free component and a non-context-free component. From one transformation, the non-context-free component results with two rules of the form 11 → 00 and 0000 → 2222, while the other transformation produces the non-context-free component with two rules of the form 11 → 00 and 0000 → eps. Apart from this significant reduction and simplification, our research describes several other useful properties concerning these systems and the way they work. We will show that the resulting systems can closely simulate their original grammar and that their sentence generation process can be handled in a parallel way.
  • Presentation: Slides (PDF)

Regular talks, 11:30 - 12:45:

• Marek Milkovič: Extraction of features from binary files and creation of detection patterns (Abstract, Slides)
• Lucie Charvát: Acceptance Power of Unlimitedly Deep Pushdown Automata (Abstract, Slides)
• František​ ​Mazura: Formal​ ​verification​ and its application in​ the security​ ​of​ information​ systems (Abstract, Slides)

• LTA 2019
• LTA 2018

• LTA 2016
• LTA 2015
• LTA 2014
• LTA 2013
• LTA 2012
• LTA 2011