Language and Automata Theory and Applications: 13th International Conference, LATA 2019, St. Petersburg, Russia, March 26-29, 2019, Proceedings (Lecture Notes in Computer Science Book 11417)

This book constitutes the refereed proceedings of the 13th International Conference on Language and Automata Theory and Applications, LATA 2019, held in St. Petersburg, Russia, in March 2019. The 31 revised full papers presented together with 5 invited talks were carefully reviewed and selected from 98 submissions. The papers cover the following topics: Automata; Complexity; Grammars; Languages; Graphs, trees and rewriting; and Words and codes. Front Matter ....Pages I-XVII Front Matter ....Pages 1-1 Modern Aspects of Complexity Within Formal Languages (Henning Fernau)....Pages 3-30 Observation and Interaction (Edward A. Lee)....Pages 31-42 From Words to Graphs, and Back (Vadim Lozin)....Pages 43-54 Front Matter ....Pages 55-55 An Oracle Hierarchy for Small One-Way Finite Automata (M. Anabtawi, S. Hassan, C. Kapoutsis, M. Zakzok)....Pages 57-69 Orbits of Abelian Automaton Groups (Tim Becker, Klaus Sutner)....Pages 70-81 Bounded Automata Groups are co-ET0L (Alex Bishop, Murray Elder)....Pages 82-94 Decidability of Sensitivity and Equicontinuity for Linear Higher-Order Cellular Automata (Alberto Dennunzio, Enrico Formenti, Luca Manzoni, Luciano Margara, Antonio E. Porreca)....Pages 95-107 On Varieties of Ordered Automata (Ondřej Klíma, Libor Polák)....Pages 108-120 Automata over Infinite Sequences of Reals (Klaus Meer, Ameen Naif)....Pages 121-133 Nonuniform Families of Polynomial-Size Quantum Finite Automata and Quantum Logarithmic-Space Computation with Polynomial-Size Advice (Tomoyuki Yamakami)....Pages 134-145 Equivalence Checking of Prefix-Free Transducers and Deterministic Two-Tape Automata (Vladimir A. Zakharov)....Pages 146-158 Efficient Symmetry Breaking for SAT-Based Minimum DFA Inference (Ilya Zakirzyanov, Antonio Morgado, Alexey Ignatiev, Vladimir Ulyantsev, Joao Marques-Silva)....Pages 159-173 Front Matter ....Pages 175-175 Closure and Nonclosure Properties of the Compressible and Rankable Sets (Jackson Abascal, Lane A. Hemaspaandra, Shir Maimon, Daniel Rubery)....Pages 177-189 The Range of State Complexities of Languages Resulting from the Cut Operation (Markus Holzer, Michal Hospodár)....Pages 190-202 State Complexity of Pseudocatenation (Lila Kari, Timothy Ng)....Pages 203-214 Complexity of Regex Crosswords (Stephen Fenner, Daniel Padé)....Pages 215-230 Front Matter ....Pages 231-231 Generalized Predictive Shift-Reduce Parsing for Hyperedge Replacement Graph Grammars (Berthold Hoffmann, Mark Minas)....Pages 233-245 Transformation of Petri Nets into Context-Dependent Fusion Grammars (Hans-Jörg Kreowski, Sabine Kuske, Aaron Lye)....Pages 246-258 Generalized Register Context-Free Grammars (Ryoma Senda, Yoshiaki Takata, Hiroyuki Seki)....Pages 259-271 Front Matter ....Pages 273-273 Logic and Rational Languages of Scattered and Countable Series-Parallel Posets (Amazigh Amrane, Nicolas Bedon)....Pages 275-287 Toroidal Codes and Conjugate Pictures (Marcella Anselmo, Maria Madonia, Carla Selmi)....Pages 288-301 Geometrical Closure of Binary \(V_{3/2}\) Languages (Jean-Philippe Dubernard, Giovanna Guaiana, Ludovic Mignot)....Pages 302-314 Deterministic Biautomata and Subclasses of Deterministic Linear Languages (Galina Jirásková, Ondřej Klíma)....Pages 315-327 Learning Unions of k-Testable Languages (Alexis Linard, Colin de la Higuera, Frits Vaandrager)....Pages 328-339 Front Matter ....Pages 341-341 Regular Matching and Inclusion on Compressed Tree Patterns with Context Variables (Iovka Boneva, Joachim Niehren, Momar Sakho)....Pages 343-355 Rule-Based Unification in Combined Theories and the Finite Variant Property (Ajay K. Eeralla, Serdar Erbatur, Andrew M. Marshall, Christophe Ringeissen)....Pages 356-367 Extensions of the Caucal Hierarchy? (Paweł Parys)....Pages 368-380 Tight Bounds on the Minimum Size of a Dynamic Monopoly (Ahad N. Zehmakan)....Pages 381-393 Front Matter ....Pages 395-395 Recurrence in Multidimensional Words (Émilie Charlier, Svetlana Puzynina, Élise Vandomme)....Pages 397-408 A Note with Computer Exploration on the Triangle Conjecture (Christophe Cordero)....Pages 409-420 Efficient Representation and Counting of Antipower Factors in Words (Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, Wiktor Zuba)....Pages 421-433 On the Maximum Number of Distinct Palindromic Sub-arrays (Kalpana Mahalingam, Palak Pandoh)....Pages 434-446 Syntactic View of Sigma-Tau Generation of Permutations (Wojciech Rytter, Wiktor Zuba)....Pages 447-459 Palindromic Subsequences in Finite Words (Clemens Müllner, Andrew Ryzhikov)....Pages 460-468 Back Matter ....Pages 469-470