*"Introduction to the automata theory and biomolecular automata",*

**Sebastian Sakowski**

Στο πλαίσιο της διοργάνωσης των σεμιναρίων του τμήματος θα πραγματοποιηθεί την Τετάρτη 20/09/2017 και ώρα 12:00 στην αίθουσα Σεμιναρίων του Τμήματος Μηχανικών Η/Υ και Πληροφορικής, ομιλία με τίτλο "Introduction to the automata theory and biomolecular automata". Ομιλητής θα είναι ο κ.Sebastian Sakowski, Faculty of Mathematics and Computer Science University of Łódź, Poland.

*ΠΕΡΙΛΗΨΗ*

The development of conventional, silicon-based computers is limited by several barriers, including those following from the Heisenberg uncertainty principle and von Neumann “bottleneck”. Biomolecular computers, based on DNA and proteins are largely free of these disadvantages and along with quantum computers are reasonable alternatives to their conventional counterparts in some applications. In 1994 L. Adleman was the first who solved the combinatorial problem of the existence of a Hamilton path in a graph by means of adequately designed chains of DNA molecules and using well-known biochemical operations on them. Since that time there have appeared many scientific papers which have offered solutions to other problems known in computer science with the use of DNA. For example DNA computation has been used to solve Knight problem, the tic-tac-toe algorithm, or general SAT problem. Major challenges in DNA computing are constructions of models according to the Chomsky hierarchy e.g. Turing machines, pushdown automata and finite automata. A part of the above constructions present only theoretical solutions, while other ones were tested in laboratories. As regards this domain, the elaboration of a 2-state 2-symbol autonomous and programmable finite automaton by a team of scientists of the Weizmann Institute, led by E. Shapiro, was a significant event. The automaton built on DNA, was tested in a laboratory. Its action is based on cyclic cutting and ligating of DNA molecules. Its distinctive features included the fact that it was programmable (it means we may choose arbitrarily transitions of any twostate automaton), as well as autonomous (the activity of the automaton does not require man’s intervention during calculations). In the lecture will be presented results of the research in the DNA Computing area and elements of classical automata theory, languages and computation e.g. finite automata, pushdown automata and so on.

ΣΥΝΗΜΜΕΝΑ: