Abstracts of Reports and other materials of the 7th School "Computer Science Days in Ekaterinburg"
This volume of Lecture Notes in Computer Science contains the papers presented at the 22nd International Conference on Developments in Language Theory (DLT 2018) organized by the Algorithmic “Oritatami” Self-Assembly Laboratory as part of the 100th Anniversary Commemorative Events of University of Electro-Communications (UEC) in Fuchu, Tokyo, Japan, during September 10–14, 2018.
The DLT conference series is one of the major international conference series in language theory and related areas. Since its establishment by G. Rozenberg and A. Salomaa in Turku (1993), it had been held every other year in Magdeburg (1995), Thessaloniki (1997), Aachen (1999), and Vienna (2001). In 2002, the DLT conference was held in Kyoto, for the first time outside Europe. Since then, the DLT conferences have been held in and outside Europe alternately: Szeged (2003), Auckland (2004), Palermo (2005), Santa Barbara (2006), Turku (2007), Kyoto (2008), Stuttgart (2009), London (2010), Milan (2011), Taipei (2012), Marne-la-Vallée (2013), Ekaterinburg (2014), Liverpool (2015), Montréal (2016), and Liège (2017). Thus, it returned to Japan after an absence of 10 years.
The series of International Conference on Developments in Language Theory (DLT) provides a forum for presenting current developments in formal languages and automata. Its scope is very general and includes, among others, the following topics and areas: combinatorial and algebraic properties of words and languages; grammars, acceptors, and transducers for strings, trees, graphs, arrays; algebraic theories for automata and languages; codes; efficient text algorithms; symbolic dynamics; decision problems; relationships to complexity theory and logic; picture description and anal- ysis; polyominoes and bidimensional patterns; cryptography; concurrency; cellular automata; bio-inspired computing; and quantum computing.
There were 84 qualified submissions, among which three were withdrawn, from 28 countries: Australia, Austria, Belgium, Canada, China, Czech Republic, Finland, France, Germany, Hungary, India, Israel, Italy, Japan, Latvia, Luxembourg, Norway, Paraguay, Poland, Portugal, Qatar, Republic of Korea, Russia, Slovakia, South Africa, Sweden, the UK, and the USA. Each of the 81 submissions was reviewed by at least three reviewers and thoroughly discussed by the Program Committee (PC). The committee decided to accept 39 papers for oral presentation. The volume also includes the abstracts or full papers of the six invited talks given by Tomohiro I., Bakhadyr Khoussainov, Alexander Okhotin, Dominique Perrin, Marinella Sciortino, and Andrew Winslow.
We warmly thank all the invited speakers and all authors of the submitted papers for making DLT 2018 successful. As the PC chair, I, Shinnosuke Seki, would like to express my cordial gratitude to the members of the PC and the external reviewers for reviewing the papers, participating in the selection process, and helping to maintain the high standard of the DLT conferences. We appreciate the help of the EasyChair con- ference system for facilitating our work of organizing DLT 2018 very much. We would
like to thank the editorial staff of Springer, and in particular Alfred Hofmann, Anna Kramer, Christine Reiss, and Raghuram Balasubramanian for their guidance and help during the process of publishing this volume. We also would like to thank Norio Takano, the mayor of Fuchu, the staff of Fuchu City Office, and all the citizens of the city for letting us use their Baltic hall as a venue for DLT 2018. Last but not the least, we are grateful to the Organizing Committee members: Szilard Zsolt Fazekas, Satoshi Kobayashi, Kohei Maruyama, Yusei Masuda, Reoto Morita, Shiho Sugimoto, Yuki Ubukata, and Fumie Watanabe.
DLT 2018 was financially supported by the National Institute of Information and Communications Technology (NICT), the Telecommunications Advancement Foun- dations (TAF), Japan Society for the Promotion of Science (JSPS) as Grant-in-Aid for Young Scientists (A) No. 16H05854 and Grant-in-Aid for Challenging Research (Exploratory) No. 18K19779 to Shinnosuke Seki, Kubota Information Technology, and the University of Electro-Communications. We would like to express our sincere gratitude for their philanthropic support.
We are all looking forward to DLT 2019 at the University of Warsaw in Poland.
September 2018 Mizuho Hoshi Shinnosuke Seki
The 21st International Conference on Developments in Language Theory (DLT 2017) was organized by the Department of Mathematics of the University of Liège, Belgium, during August 7–11, 2017.
The DLT conference series is one of the major international conference series in language theory and related areas. The DLT conference was established by G. Rozenberg and A. Salomaa in 1993. Since then, the DLT conferences have been held on every odd year: Magdeburg, Germany (1995), Thessaloniki, Greece (1997), Aachen, Germany (1999), and Vienna, Austria (2001). Since 2001, a DLT conference has been taking place in Europe on every odd year and outside Europe on every even year. The locations of DLT conferences since 2002 were: Kyoto, Japan (2002), Szeged, Hungary (2003), Auckland, New Zealand (2004), Palermo, Italy (2005), Santa Barbara, California, USA (2006), Turku, Finland (2007), Kyoto, Japan (2008), Stuttgart, Ger- many (2009), London, Ontario, Canada (2010), Milan, Italy (2011), Taipei, Taiwan (2012), Marne-la-Vallée, France (2013), Ekaterinburg, Russia (2014), Liverpool, UK (2015), and Montréal, Canada (2016). This 21st edition was thus the first time that the conference was organized in Belgium.
The series of International Conferences on Developments in Language Theory provides a forum for presenting current developments in formal languages and auto- mata. Its scope is very general and includes, among others, the following topics and areas: combinatorial and algebraic properties of words and languages; grammars, acceptors and transducers for strings, trees, graphs, arrays; algebraic theories for automata and languages; codes; efficient text algorithms; symbolic dynamics; decision problems; relationships to complexity theory and logic; picture description and anal- ysis; polyominoes and bidimensional patterns; cryptography; concurrency; cellular automata; bio-inspired computing; quantum computing.
The papers submitted to DLT 2017 were from 19 countries including Belgium, Canada, Czech Republic, France, Germany, Hungary, India, Italy, Japan, The Netherlands, Poland, Portugal, Republic of Korea, Russia, Slovakia, South Africa, Thailand, and USA.
This volume of Lecture Notes in Computer Science contains the papers that were presented at DLT 2017. There were 47 qualified submissions. Each submission was handled by three Program Committee members and received at least three reviews. The committee decided to accept 24 papers. The volume also includes the abstracts or full papers of the invited speakers:
– Véronique Bruyère (University of Mons): “Computer-Aided Synthesis: A Game-Theoretic Approach”
– Sergei Kitaev (University of Strathclyde): “A Comprehensive Introduction to the Theory of Word-Representable Graphs”
– Robert Mercaş (Loughborough University): “On the Number of Factors with Maximal-Exponent in Words”
– Balasubramanian Ravikumar (Sonoma State University): “Language Approxima- tion: Asymptotic and Non-asymptotic Results”
– Eric Rowland (Hofstra University): “Binomial Coefficients, Valuations, and Words”
– Michał‚ Skrzypczak (University of Warsaw): “Connecting Decidability and Com- plexity for MSO Logic”
We warmly thank all the invited speakers and all the authors of the submitted papers. We also would like to thank all the members of the Program Committee and all the external reviewers (listed in the proceedings) for their excellent work in evaluating the papers. We finally thank all the members of the Organizing Committee at the University of Liège.
The organization of the conference benefited from the support of the F.R.S.-FNRS, the Faculty of Sciences of the University of Liège and the Research Unit in Mathe- matics of the University of Liège. The reviewing process was organized using the EasyChair conference system created by Andrei Voronkov. We would like to acknowledge that this system greatly helped to improve the efficiency of the committee work. Finally, we wish to thank the editors of the Lecture Notes in Computer Science series and Springer.
Émilie Charlier Julien Leroy Michel Rigo
Lexicographically minimal and lexicographically maximal suffixes of a string are fundamental notions of stringology. It is well known that the lexicographically minimal and maximal suffixes of a given string S can be computed in linear time and space by constructing a suffix tree or a suffix array of S. Here we consider the case when S is a substring of another string T of length n.We propose two linear-space data structures for T which allow to compute the minimal suffix of S in O(log^1+ε n) time (for any fixed ε > 0) and the maximal suffix of S in O(log n) time. Both data structures take O(n) time to construct.
We consider regular realizability problems, which consist in verifying whether the intersection of a regular language which is the problem input and a fixed language (filter) which is a parameter of the problem is nonempty. We study the algorithmic complexity of regular realizability problems for context-free filters. This characteristic is consistent with the rational dominance relation of CF languages. However, as we prove, it is more rough. We also give examples of both P-complete and NL-complete regular realizability problems for CF filters. Furthermore, we give an example of a subclass of CF languages for filters of which the regular realizability problems can have an intermediate complexity. These are languages with polynomially bounded rational indices.
Timed automata and timed finite state machins (TFSMs) have been proposed to represent more accurately the behaviour of systems in continuous time. Recently, we introduced a model of TFSMs that extends the expressive power of FSMs by introducing a single clock, timed guards which restrict when the input/output transitions may happen, and timeouts on the transitions. We derived an abstraction procedure to convert a TFSM into an equivalent untimed FSM. Here, we extend the model with output timeouts and derive a minimal form for deterministic TFSMs that reduces the number of states, the number of transitions and the timeout values at each state.
The present article continues the investigation of the Soqotri verbal system undertaken by the Russian-Soqotri fieldwork team. The article focuses on the so-called “weak” and “geminated” roots in the basic stem. The investigation is based on the analysis of full paradigms (perfect, imperfect and jussive) of more than 170 “weak” and “geminated” Soqotri verbs.