Descriptional Complexity of Formal Systems: 20th IFIP WG 1.02 International Conference, DCFS 2018, Halifax, NS, Canada, July 25–27, 2018, Proceedings (Lecture Notes in Computer Science Book 10952)

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. Front Matter ....Pages I-XIV Finite Automata and Randomness (Ludwig Staiger)....Pages 1-10 Properties of Right One-Way Jumping Finite Automata (Simon Beier, Markus Holzer)....Pages 11-23 Word Problem Languages for Free Inverse Monoids (Tara Brough)....Pages 24-36 Most Complex Deterministic Union-Free Regular Languages (Janusz A. Brzozowski, Sylvie Davies)....Pages 37-48 Site-Directed Insertion: Decision Problems, Maximality and Minimality (Da-Jung Cho, Yo-Sub Han, Kai Salomaa, Taylor J. Smith)....Pages 49-61 Two-Way Automata over Locally Finite Semirings (Louis-Marie Dando, Sylvain Lombardy)....Pages 62-74 A New Technique for Reachability of States in Concatenation Automata (Sylvie Davies)....Pages 75-87 Forward Injective Finite Automata: Exact and Random Generation of Nonisomorphic NFAs (Miguel Ferreira, Nelma Moreira, Rogério Reis)....Pages 88-100 On the Generation of 2-Polyominoes (Enrico Formenti, Paolo Massazza)....Pages 101-113 A Local Limit Property for Pattern Statistics in Bicomponent Stochastic Models (Massimiliano Goldwurm, Jianyi Lin, Marco Vignati)....Pages 114-125 Linear-Time Limited Automata (Bruno Guillon, Luca Prigioniero)....Pages 126-138 Cover Complexity of Finite Languages (Stefan Hetzl, Simon Wolfsteiner)....Pages 139-150 On the Grammatical Complexity of Finite Languages (Markus Holzer, Simon Wolfsteiner)....Pages 151-162 State Grammars with Stores (Oscar H. Ibarra, Ian McQuillan)....Pages 163-174 Error-Free Affine, Unitary, and Probabilistic OBDDs (Rishat Ibrahimov, Kamil Khadiev, Krišjānis Prūsis, Abuzer Yakaryılmaz)....Pages 175-187 State Complexity of Unambiguous Operations on Deterministic Finite Automata (Galina Jirásková, Alexander Okhotin)....Pages 188-199 Cycle Height of Finite Automata (Chris Keeler, Kai Salomaa)....Pages 200-211 Finite Automata with Undirected State Graphs (Martin Kutrib, Andreas Malcher, Christian Schneider)....Pages 212-223 Further Closure Properties of Input-Driven Pushdown Automata (Alexander Okhotin, Kai Salomaa)....Pages 224-236 State Complexity Characterizations of Parameterized Degree-Bounded Graph Connectivity, Sub-Linear Space Computation, and the Linear Space Hypothesis (Tomoyuki Yamakami)....Pages 237-249 Back Matter ....Pages 251-251