Invited speakers

Alica Kelemenová (Institute of Computer Science, Opava): Variants of grammar systems - motivations and problems

Grammar systems form an important part of investigation of formal aspects of multi-agent systems. Cooperation, distribution and complexity are basic research topics of grammar systems. Study of grammar systems started in the 90-ties of the last century with motivation of black board architecture. Recently the theory covers different types of systems motivated by technology as well as by biology. We introduce some representative variants of grammar systems, e.g. colonies, eco-grammar systems, membrane systems. We illustrate different behavior of these systems, sequential, parallel behavior, and their more complex combinations, based on the motivation to introduce systems. We recapitulate some representative research topics, typical and interesting results, including provocative open problems and rich references.

Alica Kelemenová graduated in mathematics (Šafárik University, Košice, Slovakia). She received the RNDr. title (Comenius University, Bratislava), the degree CSc. (PhD equivalent, Slovak Academy of Sciences, Bratislava). During 1972-1994 at the Mathematical Institute of the Slovak Academy of Science formal language and automata theory formed her professional interest (famous Černý conjecture for finite automata and description complexity of languages). At present she is the professor of computer science and senior researcher at the Silesian University, Opava, Czech Republic. Her present research interest includes formal language theory, Lindenmayer systems, P systems and covers study of decentralization and cooperation in various types of grammar systems.

Erzsébet Csuhaj-Varjú (Eötvös Loránd University, Budapest): P Systems: Bio-inspired Computational Models for Complex Systems

The theory of P systems or membrane systems is a vivid scientific area in bio-inspired computing, dealing with computational models inspired by architecture and functioning of living cells and tissues. The basic variant of a P system consists of a hierarchically embedded structure of membranes where each membrane encloses a region which contains multisets of objects and might also contain other membranes. There are rules associated to the regions describing the evolution and communication of the objects present in the regions. The evolution of the system corresponds to a computation. These constructs model living cells. Tissue-like P systems represent networks of evolving cells embedded in a joint shared environment; cells also correspond to agents. Regions of cell-like P systems can also be considered dynamically changing agents which are in interaction with their local environment, i.e. neighbouring regions or the environment of the entire P system.
In the talk we discuss why some important variants of P systems (P colonies, purely communicating P systems, networks of cells) can be considered as models of complex natural systems. P colonies are variants of very simple tissue-like P systems, representing communities of very simple reactive agents that live and act in a joint shared environment. In case of purely communicating P systems, the objects in the regions or in the cells do not evolve but only move from their location to their (local) environment (to certain region or cell). We give a summary of the most relevant results concerning these constructs and also provide their interpretation in terms of complex systems. We propose open problems and new directions for future research as well.

Erzsébet Csuhaj-Varjú is a full professor at the Faculty of Informatics, Eötvös Loránd University, Budapest, Hungary and head of the Doctoral School of Informatics of the University.
Her main research interests are formal languages and applications, bio-inspired computing and distributed systems. In these areas she authored and co-authored more than two hundred and twenty publications (articles in international journals and edited volumes and a monograph) and she was editor or co-editor of eighteen volumes. She has been co-founder of the area of grammar systems, a formal language-theoretic counterpart of the theory of multi-agent systems. She also has important contributions to bio-inspired computing; among others together with her co-authors, she have launched research vistas theory of networks of language processors and P automata (membrane automata) theory.
She has been the supervisor (principal investigator) and participant of several Hungarian and bilateral granted research projects, team leader or leader of EU projects. She is the chair of the Advisory Board of the International Membrane Computing Society. She is member of the editorial board of International Journal of Foundations of Computer Science and Journal of Membrane Computing. In the last twelve years, she has been programme committee member and organizer of more than fifty international workshops and conferences, among them she was programme committee co-chair and chair of the organizing committee of FCT 2007, AFL 2008, CMC13, CiE 2014, MFCS 2014, AFL 2017.
She is serving as member in several scientific/educational committees of the Eötvös Loránd University and she is the chair of the Committee of Information Science, Section of Mathematics of the Hungarian Academy of Sciences.

Friedrich Otto (University Kassel, Germany): 25 Years of Restarting Automata: Lots of Results and Open Problems

The restarting automaton was introduced by Petr Jančar, František Mráz, Martin Plátek, and Jörg Vogel in a talk presented at the FCT'95. It is not just another variant of the Turing machine, but it is a machine model that is motivated by the linguistic technique of analysis by reduction.Given a sentence of a natural language, possibly annotated by tags giving morphological, syntactical, and/or semantical information on the various word forms (morphemes) of the sentence, this sentence is repeatedly simplified by local transformations until either an error is detected and the input sentence is rejected, or a correct simple sentence is obtained and the input sentence is accepted. Accordingly, a restarting automaton consists of a flexible tape (or a linked list) that initially contains the input, a finite-state control, and a read/write window of a fixed positive size. It scans the current sentence stored on its tape, performs one or more local transformations, in this way simplifying the stored sentence, and then it restarts, which means that it places its read/write window on the beginning of its tape and resets its finite-state control to the initial state. This sequence of operations, called a cycle, is iterated until the automaton either accepts or rejects.

Actually, the restarting automaton is not simply an automaton, but a whole family of different types of automata. These types differ with respect to the allowed move and rewrite operations, the size of the read/write window, the number of allowed rewrite operations between restarts, the number of non-input symbols in the tape alphabet of the automaton, and the number of states. Without any restrictions on the allowed rewrite operations, the restarting automaton is equivalent to the Turing machine. In order to restrict the expressive capacity of the restarting automaton, it is therefore generally required that each rewrite operation allowed is weight-reducing or even length-reducing. Using different restrictions the classes of the Chomsky hierarchy have been characterized by various types of restarting automata. In the present talk, these characterizations are presented by considering some of the parameters that are used to specify different types of restarting automata. In addition, the recently introduced notions of h-lexicalized restarting automata and h-lexicalized syntactic analysis, which are motivated by the idea that all non-input symbols of a restarting automaton should have some linguistically meaningful interpretation, are discussed.

Friedrich Otto is now a retired but still scientifically very active professor at University Kassel, Germany. Since his graduation in 1978 at the University of Kaiserslautern, he was interested in algorithmic questions on groups and rewriting systems. His monograph “String Rewriting Systems” co-authored with Ronald V. Book and published in 1993 belongs to the standard literature. Besides the above universities, he lectured two years at the State University of New York at Albany and one term in Prague. Early after the first publications on restarting automata, he has founded a group working on this topic in Kassel. Since 2003 he cooperated on this research with a group in Prague, Czech Republic. Most of the important results in the field of restarting automata were obtained by him or in cooperation with him. He has spread the methods from restarting automata to CD-systems, tree automata, and picture languages. Besides the above monograph, Friedrich Otto published more than 230 scientific papers and supervised ten Ph.D. theses. He chaired, between 2003 and 2009, the Steering Committee of the special interest group on Automata and Formal Languages of the German Gesellschaft fűr Informatik. In 1999 and 2010, he organized the annual meeting of the special interest group called Theorietag "Automaten and Formale Sprachen". Friedrich Otto is a co-founder of the series of workshops on Non-Classical Models of Automata and Applications, which took place annually since 2007.

Francesco Dolce (Faculty of Nuclear Sciences and Physical Engineering, Czech Technical University in Prague) : Interval Exchange Transformations: from Symbolic Dynamics to Combinatorics

An Interval Exchange Transformations, or IET, is a dynamical system obtained by iterating simple geometric transformations on an interval. Such kind of system can be seen as a generalization of the rotation of the circle.
Using an operation called "natural coding", one can obtain from an interval exchange transformation a formal language and a shift space, both satisfying interesting and peculiar properties.
In this talk we use IETs to describe the connections between symbolic dynamics and combinatorics on words, using tools ranging from formal language theory to ergodic theory.
We also introduce Rauzy induction on a IET, which can be viewed as a generalization of the continued faction expansion.

Francesco Dolce graduated both in Mathematics (Università di Palermo, Italy) and in Computer Science (Université Paris-Est Marne-la-Vallée, France).
After a PhD in Theoretical Computer Science (Université Paris-Est, France) he worked between France (Université Paris-Diderot) and Canada (Université du Québec A Montréal and McGill University). In Montréal he was part of the organizing committee of WORDS 2017. Since 2019 he is a postdoc the Faculty of Nuclear Sciences and Physical Engineering of the Czech Technical University in Prague (Czech Republic)
His research interests span between Combinatorics on Words, Formal Languages, Variable-Length Codes, Automata and Symbolic Dynamical Systems.