О вычислительной сложности языков, распознаваемых автоматами со словарём (Set Automata)
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 textbook contains the basic information of formal logical systems. It is Boolean functions, Post’s theorem on functional completeness, the k-valued logic, derivatives of Boolean functions, axiomatic calculi for propositions, for predicates, for sequentions, for resolutions. Programming language Prolog and axiomatic programming language OBJ3 are introduced. Problems of monadic logic, of finite automata and of the represented by them languages, of temporal logic are considered. Many examples are shown. It is put in a basis of the book long-term experience of teaching by authors the discipline «Discrete mathematics» at the business informatics faculty, at the computer science faculty of National research university Higher school of economics, and at the automatics and computer technique faculty of National research university Moscow power engineering institute. The book is intended for the students of a bachelor degree, trained at the computer science faculties in the directions 09.03.01 Informatics and computational technique, 09.03.02 Informational systems and technologies, 09.03.03 Applied informatics, 09.03.04 Software Engineering, and also for IT experts and developers of software products.
The collection represents proceedings of the 5th school-seminar "Syntax and Semantics of Logic Systems" (Ulan-Ude, 08.08.2017 - 12.08.2017). The conference subject area includes: theory of models and universal algebra; theory of boolean and finite-valued functions; formal languages and logic calculus; mathematical logic in education.
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.