Developments in language theory : 23rd International Conference, DLT 2019, Warsaw, Poland, August 5-9, 2019 : proceedings

This book constitutes the proceedings of the 23rd International Conference on Developments in Language Theory, DLT 2019, held in Warsaw, Poland, in August 2019. The 20 full papers presented together with three invited talks were carefully reviewed and selected from 30 submissions. The papers cover the following topics and areas: combinatorial and algebraic properties of words and languages; grammars, acceptors and transducers for strings, trees, graphics, arrays; algebraic theories for automata and languages; codes; efficient text algorithms; symbolic dynamics; decision problems; relationships to complexity theory and logic; picture description and analysis, polyominoes and bidimensional patterns; cryptography; concurrency; celluar automata; bio-inspired computing; quantum computing. -- Provided by publisher Front Matter ....Pages i-x Front Matter ....Pages 1-1 Inherent Size Blowup in \(\omega \)-Automata (Udi Boker)....Pages 3-17 Deciding Context Unification (with Regular Constraints) (Artur Jeż)....Pages 18-40 Single-Stranded Architectures for Computing (Shinnosuke Seki)....Pages 41-56 Front Matter ....Pages 57-57 A Linear Bound on the K-Rendezvous Time for Primitive Sets of NZ Matrices (Umer Azfar, Costanza Catalano, Ludovic Charlier, Raphaël M. Jungers)....Pages 59-73 Words of Minimum Rank in Deterministic Finite Automata (Jarkko Kari, Andrew Ryzhikov, Anton Varonka)....Pages 74-87 On the Length of Shortest Strings Accepted by Two-Way Finite Automata (Egor Dobronravov, Nikita Dobronravov, Alexander Okhotin)....Pages 88-99 Characterizing the Valuedness of Two-Way Finite Transducers (Di-De Yen, Hsu-Chun Yen)....Pages 100-112 Input-Driven Pushdown Automata for Edit Distance Neighborhood (Viliam Geffert, Zuzana Bednárová, Alexander Szabari)....Pages 113-126 The Relative Edit-Distance Between Two Input-Driven Languages (Hyunjoon Cheon, Yo-Sub Han, Sang-Ki Ko, Kai Salomaa)....Pages 127-139 On Shrinking Restarting Automata of Window Size One and Two (František Mráz, Friedrich Otto)....Pages 140-153 The Teaching Complexity of Erasing Pattern Languages with Bounded Variable Frequency (Ziyuan Gao)....Pages 154-167 On Timed Scope-Bounded Context-Sensitive Languages (D. Bhave, S. N. Krishna, R. Phawade, A. Trivedi)....Pages 168-181 Logics for Reversible Regular Languages and Semigroups with Involution (Paul Gastin, Amaldev Manuel, R. Govind)....Pages 182-191 Eventually Safe Languages (Simon Iosti, Denis Kuperberg)....Pages 192-205 Coinductive Algorithms for Büchi Automata (Denis Kuperberg, Laureline Pinault, Damien Pous)....Pages 206-220 Hole-Free Partially Directed Animals (Paolo Massazza)....Pages 221-233 First Lower Bounds for Palindromic Length (Anna E. Frid)....Pages 234-243 On Palindromic Length of Sturmian Sequences (Petr Ambrož, Edita Pelantová)....Pages 244-250 Separating Many Words by Counting Occurrences of Factors (Aleksi Saarela)....Pages 251-264 k-Spectra of Weakly-c-Balanced Words (Joel D. Day, Pamela Fleischmann, Florin Manea, Dirk Nowotka)....Pages 265-277 Computing the k-binomial Complexity of the Thue–Morse Word (Marie Lejeune, Julien Leroy, Michel Rigo)....Pages 278-291 Context-Free Word Problem Semigroups (Tara Brough, Alan J. Cain, Markus Pfeiffer)....Pages 292-305 Analysis of Symbol Statistics in Bicomponent Rational Models (M. Goldwurm, J. Lin, M. Vignati)....Pages 306-318 Back Matter ....Pages 319-319 This book is a photographic reproduction of the book of the same title published in 1981, for which there has been continuing demand on account of its accessible technical level. Its appearance also helped generate considerable subsequent work on inhomogeneous products of matrices. This printing adds an additional bibliography on coefficients of ergodicity and a list of corrigenda. Eugene Seneta received his Ph. D. in 1968 from the Australian National University. He left Canberra in 1979 to become Professor and Head of the Department of Mathematical Statistics at the University of Sydney. He has been a regular visitor to the United States, most frequently to the University of Virginia. Now Emeritus Professor at the University of Sydney, he has recently developed a renewed interest in financial mathematics. He was elected Fellow of the Australian Academy of Science in 1985 and awarded the Pitman Medal of the Statistical Society of Australia for his distinguished research contributions. The first edition of this book, entitled Non-Negative Matrices, appeared in 1973, and was followed in 1976 by his Regularly Varying Functions in the Springer Lecture Notes in Mathematics, later translated into Russian. Both books were pioneering in their fields. In 1977, Eugene Seneta coauthored (with C.C. Heyde) I.J. Bienaymé : Statistical Theory Anticipated, which is effectively a history of probability and statistics in the 19th century, and in 2001 co-edited with the same colleague Statisticians of the Centuries, both published by Springer. Having served on the editorial board of the Encyclopedia of Statistical Science, he is currently Joint Editor of the International Statistical Review This book develops a theory of formal power series in noncommuting variables, the main emphasis being on results applicable to automata and formal language theory. This theory was initiated around 196O-apart from some scattered work done earlier in connection with free groups-by M. P. Schutzenberger to whom also belong some of the main results. So far there is no book in existence concerning this theory. This lack has had the unfortunate effect that formal power series have not been known and used by theoretical computer scientists to the extent they in our estimation should have been. As with most mathematical formalisms, the formalism of power series is capable of unifying and generalizing known results. However, it is also capable of establishing specific results which are difficult if not impossible to establish by other means. This is a point we hope to be able to make in this book. That formal power series constitute a powerful tool in automata and language theory depends on the fact that they in a sense lead to the arithmetization of automata and language theory. We invite the reader to prove, for instance, Theorem IV. 5. 3 or Corollaries III. 7. 8 and III. 7.- all specific results in language theory-by some other means. Although this book is mostly self-contained, the reader is assumed to have some background in algebra and analysis, as well as in automata and formal language theory. Since its inception by Perron and Frobenius, the theory of non-negative matrices has developed enormously and is now being used and extended in applied fields of study as diverse as probability theory, numerical analysis, demography, mathematical economics, and dynamic programming, while its development is still proceeding rapidly as a branch of pure mathematics in its own right. While there are books which cover this or that aspect of the theory, it is nevertheless not uncommon for workers in one or another branch of its development to be unaware of what is known in other branches, even though there is often formal overlap. One of the purposes of this book is to relate several aspects of the theory, insofar as this is possible. The author hopes that the book will be useful to mathematicians; but in particular to the workers in applied fields, so the mathematics has been kept as simple as could be managed. The mathematical requisites for reading it are: some knowledge of real-variable theory, and matrix theory; and a little knowledge of complex-variable; the emphasis is on real-variable methods. (There is only one part of the book, the second part of 55.5, which is of rather specialist interest, and requires deeper knowledge.) Appendices provide brief expositions of those areas of mathematics needed which may be less g- erally known to the average reader. This book constitutes the proceedings of the 20th International Conference on Descriptional Complexity of Formal Systems, DCFS 2018, held in Halifax, NS, Canada, in July 2018. The 19 full papers presented were carefully reviewed and selected from 24 submissions. DCFS is an annual international working conference concerning the descriptional complexity of formal systems and structures and its applications. Topics of interest are related to all aspects of descriptional complexity and much more.