Event Details
B. Nagy - Watson-Crick Automata
Seminář FM
Place
room E112 & C228, FIT VUT v Brně, Božetěchova 2,, Božetěchova 2, 612 00 Brno, CZ
Organiser
Type
seminar
Access
free
Description
The seminar (as a part of LTA 2017) 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.
(1) Lecture
Title: Linear context-free languages and Watson-Crick automata
Time & Place: November 22, 2017, 13:00-13:50, room E112, FIT VUT, Brno, Božetěchova 2
Lecturer: Dr. Benedek Nagy (Eastern Mediterranean University, North Cyprus)
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.
(2) Research Talk
Title: On 5' -> 3' Watson-Crick finite and pushdown automata
Time & Place: November 22, 2017, 14:00-15:30, room C228, FIT VUT, Brno, Božetěchova 2
Author: Dr. Benedek Nagy (Eastern Mediterranean University, North Cyprus)
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.
Title: Linear context-free languages and Watson-Crick automata
Time & Place: November 22, 2017, 13:00-13:50, room E112, FIT VUT, Brno, Božetěchova 2
Lecturer: Dr. Benedek Nagy (Eastern Mediterranean University, North Cyprus)
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.
(2) Research Talk
Title: On 5' -> 3' Watson-Crick finite and pushdown automata
Time & Place: November 22, 2017, 14:00-15:30, room C228, FIT VUT, Brno, Božetěchova 2
Author: Dr. Benedek Nagy (Eastern Mediterranean University, North Cyprus)
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.