## Events## B. Nagy - Watson-Crick Automata
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) LectureTitle: Linear context-free languages and Watson-Crick automataTime & Place: November 22, 2017, 13:00-13:50, room E112, FIT VUT, Brno, Božetěchova 2Lecturer: 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 TalkTitle: On 5' -> 3' Watson-Crick finite and pushdown automataTime & Place: November 22, 2017, 14:00-15:30, room C228, FIT VUT, Brno, Božetěchova 2Author: 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. |