Book
Вычислительные процессы: теория трансляции, управление данными и сети Петри
Concepts of the theory of algorithmic languages and methods of broadcasting and also processing of data and their organization are considered. Statement of material is followed by practical examples. The grant is intended for students of the higher educational institutions studying in the Applied Mathematics and Applied Mathematics and Informatics directions. Contains the subjects studied in disciplines "The theory of computing processes and structures", "The theory of algorithmic languages", "Mathematical fundamentals of informatics". It can be used as lecture material, on a practical training, when performing course and theses and also as means of self-education
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.
This monograph is the collection of the selected papers from Gdańsk EuroSymposium 2015 on SAND – Systems Analysis and Design. SAND is the classical field of research and education in the area of management information systems (MIS) or, as it is called more frequently in Europe – Business Informatics, almost from its origins. The objective of the EuroSymposium on Systems Analysis and Design is to promote and develop high quality research on all issues related to SAND. It provides a forum forSANDresearchers and practitioners in Europe and beyond to interact, collaborate, and develop their field. Therefore, there were three organizers of the 8th EuroSymposium on Systems Analysis and Design: – SIGSAND – Special Interest Group on Systems Analysis and Design of AIS, – PLAIS – Polish Chapter of AIS, – Department of Business Informatics of University of Gdansk, Poland.
Formal language theory has a deep connection with such areas as static code analysis, graph database querying, formal verifica- tion, and compressed data processing. Many application problems can be formulated in terms of languages intersection. The Bar-Hillel theo- rem states that context-free languages are closed under intersection with a regular set. This theorem has a constructive proof and thus provides a formal justification of correctness of the algorithms for applications mentioned above. Mechanization of the Bar-Hillel theorem, therefore, is both a fundamental result of formal language theory and a basis for the certified implementation of the algorithms for applications. In this work, we present the mechanized proof of the Bar-Hillel theorem in Coq.
Process models and graphs are commonly used for modeling and visualization of processes. They may represent sets of objects or events linked with each other in some way. Wide use of models in such languages engenders necessity of tools for creating and editing them. This paper describes the model editor which allows for dealing with classical graphs, Petri nets, finite-state machines and their systems. Additionally, the tool has a list of features like simulation of Petri nets, import and export of models in different storage formats. Carassius is a modular tool which can be extended with, for example, new formalisms. In the paper one can find a detailed description of a couple of layout algorithms that can be used for visualizing Petri nets and graphs. Carassius might be useful for educational and research purposes because of its simplicity, range of features and variety of supported notations.
We present a new structural lemma for deterministic con- text free languages. From the first sight, it looks like a pumping lemma, because it is also based on iteration properties, but it has significant distinctions that makes it much easier to apply. The structural lemma is a combinatorial analogue of KC-DCF-Lemma (based on Kolmogorov complexity), presented by Li and Vit ́anyi in 1995 and corrected by Glier in 2003. The structural lemma allows not only to prove that a language is not a DCFL, but discloses the structure of DCFLs Myhill-Nerode classes.
The article considers the issues of technical product life cycle management in the field of spare parts delivery organization and management within the framework of after-sales service. It provides an examination of a Petri net model, describing the cause-effect relations between events that are linked to delivery planning and management, based on a probabilistic analytical model for after-sales service of technical products and a program-based risk analysis system based on technical and economic criteria. The result of a given model’s performance is planning of an acceptable balance between the cost and quality of products and their current maintenance, which includes detection and minimization of financial risks. An example that illustrates automated planning of spare parts delivery is given. Dynamics of operated technical products’ quantity variation is represented in the integrated graphic type, providing an opportunity to predict an average factor of technical product’s serviceability, determined both by a number of serviceable technical products in a warehouse of the customer and productivity of repair agencies. The earned value method application is proved to be an effective tool for risk analysis of schedule variance in the field of spare parts delivery. Monitoring of the earned value of finances permits to forecast not only the probability of successful completion of spare parts delivery, but also the risks of both cost and schedule variance. An example of automated risk analysis is provided. Estimated coincidence degree of actual cost and planned value is calculated by means of the effectiveness index, which is used to analyze the quality of customer’s subdivisions performance and to correct further functioning. For a selected year, the effectiveness index can be defined and optimized for the predetermined serviceability factor, assigned for every customer during the process of automated planning of spare parts delivery. The approach presented in the article can be considered quite universal, which predetermines an opportunity to apply it in order to provide solutions for product and service life cycle management problems in various organizational technical and economic systems.
We consider certain spaces of functions on the circle, which naturally appear in harmonic analysis, and superposition operators on these spaces. We study the following question: which functions have the property that each their superposition with a homeomorphism of the circle belongs to a given space? We also study the multidimensional case.
We consider the spaces of functions on the m-dimensional torus, whose Fourier transform is p -summable. We obtain estimates for the norms of the exponential functions deformed by a C1 -smooth phase. The results generalize to the multidimensional case the one-dimensional results obtained by the author earlier in “Quantitative estimates in the Beurling—Helson theorem”, Sbornik: Mathematics, 201:12 (2010), 1811 – 1836.
We consider the spaces of function on the circle whose Fourier transform is p-summable. We obtain estimates for the norms of exponential functions deformed by a C1 -smooth phase.