Developments in Language Theory: 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings (Lecture Notes in Computer Science Book 11088)

This book constitutes the proceedings of the 22nd International Conference on Developments in Language Theory, DLT 2018, held in Tokyo, Japan, in September 2018. The 39 full papers presented in this volume were carefully reviewed and selected from 84 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. Front Matter ....Pages I-XIV Block Sorting-Based Transformations on Words: Beyond the Magic BWT (Raffaele Giancarlo, Giovanni Manzini, Antonio Restivo, Giovanna Rosone, Marinella Sciortino)....Pages 1-17 The Runs Theorem and Beyond (Tomohiro I)....Pages 18-23 A Brief Excursion to Parity Games (Bakhadyr Khoussainov)....Pages 24-35 A Tale of Conjunctive Grammars (Alexander Okhotin)....Pages 36-59 Groups, Languages and Dendric Shifts (Dominique Perrin)....Pages 60-73 Some Open Problems in Polyomino Tilings (Andrew Winslow)....Pages 74-82 Weak Cost Register Automata Are Still Powerful (Shaull Almagor, Michaël Cadilhac, Filip Mazowiecki, Guillermo A. Pérez)....Pages 83-95 From Two-Way Transducers to Regular Function Expressions (Nicolas Baudru, Pierre-Alain Reynier)....Pages 96-108 Decidability of Right One-Way Jumping Finite Automata (Simon Beier, Markus Holzer)....Pages 109-120 Additive Number Theory via Approximation by Regular Languages (Jason P. Bell, Thomas F. Lidbetter, Jeffrey Shallit)....Pages 121-132 Tree-to-Graph Transductions with Scope (Johanna Björklund)....Pages 133-144 A Characterization of Completely Reachable Automata (E. A. Bondar, M. V. Volkov)....Pages 145-155 Inequalities for One-Step Products (Mário J. J. Branco, Jean-Éric Pin)....Pages 156-168 On the Commutative Equivalence of Context-Free Languages (Arturo Carpi, Flavio D’Alessandro)....Pages 169-181 Simon’s Theorem for Scattered Words (Olivier Carton, Maurice Pouzet)....Pages 182-193 The Synchronizing Probability Function for Primitive Sets of Matrices (Costanza Catalano, Raphaël M. Jungers)....Pages 194-205 Recognizability for Automata (Didier Caucal, Chloé Rispal)....Pages 206-218 Site-Directed Deletion (Da-Jung Cho, Yo-Sub Han, Hwee Kim, Kai Salomaa)....Pages 219-230 Counting Subwords and Regular Languages (Charles J. Colbourn, Ryan E. Dougherty, Thomas F. Lidbetter, Jeffrey Shallit)....Pages 231-242 Deque Languages, Automata and Planar Graphs (Stefano Crespi Reghizzi, Pierluigi San Pietro)....Pages 243-255 A General Approach to State Complexity of Operations: Formalization and Limitations (Sylvie Davies)....Pages 256-268 On Matching Generalised Repetitive Patterns (Joel D. Day, Pamela Fleischmann, Florin Manea, Dirk Nowotka, Markus L. Schmid)....Pages 269-281 Intersection Non-emptiness and Hardness Within Polynomial Time (Mateus de Oliveira Oliveira, Michael Wehar)....Pages 282-290 Complexity of Decision Problems on Totally Rigid Acyclic Tree Grammars (Sebastian Eberhard, Gabriel Ebner, Stefan Hetzl)....Pages 291-303 A Pattern Logic for Automata with Outputs (Emmanuel Filiot, Nicolas Mazzocchi, Jean-François Raskin)....Pages 304-317 The Intersection Problem for Finite Semigroups (Lukas Fleischer)....Pages 318-329 On Completely Reachable Automata and Subset Reachability (François Gonze, Raphaël M. Jungers)....Pages 330-341 On Minimal Grammar Problems for Finite Languages (Hermann Gruber, Markus Holzer, Simon Wolfsteiner)....Pages 342-353 Reversible Pushdown Transducers (Bruno Guillon, Martin Kutrib, Andreas Malcher, Luca Prigioniero)....Pages 354-365 Two-Way Automata and One-Tape Machines (Bruno Guillon, Giovanni Pighizzini, Luca Prigioniero, Daniel Průša)....Pages 366-378 Dynamics of the Independence Number and Automata Synchronization (Vladimir V. Gusev, Raphaël M. Jungers, Daniel Průša)....Pages 379-391 Closest Substring Problems for Regular Languages (Yo-Sub Han, Sang-Ki Ko, Timothy Ng, Kai Salomaa)....Pages 392-403 Computational Complexity of Decision Problems on Self-verifying Finite Automata (Markus Holzer, Sebastian Jakobi, Jozef Jirásek Jr.)....Pages 404-415 Generalizations of Checking Stack Automata: Characterizations and Hierarchies (Oscar H. Ibarra, Ian McQuillan)....Pages 416-428 On Counting Functions of Languages (Oscar H. Ibarra, Ian McQuillan, Bala Ravikumar)....Pages 429-440 Towards Exact State Complexity Bounds for Input-Driven Pushdown Automata (Galina Jirásková, Alexander Okhotin)....Pages 441-452 On Abelian Subshifts (Juhani Karhumäki, Svetlana Puzynina, Markus A. Whiteland)....Pages 453-464 Reachability Problems in Nondeterministic Polynomial Maps on the Integers (Sang-Ki Ko, Reino Niskanen, Igor Potapov)....Pages 465-477 Projection for Büchi Tree Automata with Constraints Between Siblings (Patrick Landwehr, Christof Löding)....Pages 478-490 The Computational Power of Parsing Expression Grammars (Bruno Loff, Nelma Moreira, Rogério Reis)....Pages 491-502 On Finitely Ambiguous Büchi Automata (Christof Löding, Anton Pirogov)....Pages 503-515 Uniformization Problem for Variants of First Order Logic over Finite Words (Vincent Michielini)....Pages 516-528 On Deterministic Ordered Restart-Delete Automata (Friedrich Otto)....Pages 529-540 Complementation of Finitely Ambiguous Büchi Automata (Alexander Rabinovich)....Pages 541-552 A Structural Lemma for Deterministic Context-Free Languages (Alexander A. Rubtsov)....Pages 553-565 Back Matter ....Pages 567-568