Descriptional Complexity of Formal Systems: 22nd International Conference, DCFS 2020, Vienna, Austria, August 24–26, 2020, Proceedings (Lecture Notes in Computer Science Book 12442)

This book constitutes the proceedings of the 22nd International Conference on Descriptional Complexity of Format Systems, DCFS 2020, which was supposed to take place in Vienna, Austria, in August 2020, but the conference was canceled due to the COVID-19 crisis. The 19 full papers presented in this volume were carefully reviewed and selected from 31 submissions. They deal with all aspects of descriptional complexity and costs of description of objects in various computational models, such as Turing machines, pushdown automata, finite automata, grammars, and others. Preface 6 Organization 8 Contents 10 Mutually Accepting Capacitated Automata 12 1 Introduction 12 2 Preliminaries 15 3 Expressive Power 16 3.1 Regularity 17 3.2 Determinism 17 3.3 Closure Properties 19 4 Decision Problems 20 References 23 Bad Pictures: Some Structural Properties Related to Overlaps 24 1 Introduction 24 2 Preliminaries 26 2.1 Basic Notions and Results on Strings 27 2.2 Basic Notions on Pictures 28 3 Good and Bad Pictures 29 4 Index of Bad Pictures 33 References 36 Regular Expression Length via Arithmetic Formula Complexity 37 1 Introduction 37 2 Preliminaries 39 3 Reduction to Monotone Arithmetic Formula Size 39 3.1 Bounds for Uniform Languages 41 3.2 Blow-Up of Language Operations 41 3.3 Limitations of the Arithmetic Bound 42 4 Direct Lower Bounds 43 4.1 The Divisibility Language 44 4.2 Utilizing Noncommutativity 46 5 Conclusion 46 References 48 Crisp-Determinization of Weighted Tree Automata over Additively Locally Finite and Past-Finite Monotonic Strong Bimonoids Is Decidable 50 1 Introduction 50 2 Preliminaries 52 2.1 General Notions and Notations 52 2.2 Trees and Contexts 52 2.3 Strong Bimonoids 53 3 Weighted Tree Automata with Run Semantics 54 4 Pumping Lemma 56 5 Main Result 57 References 60 On the Power of Generalized Forbidding Insertion-Deletion Systems 63 1 Introduction 63 2 Important Definitions 65 3 Main Results 66 4 Conclusions 73 References 74 State Complexity Bounds for the Commutative Closure of Group Languages 75 1 Introduction 75 2 Prerequisites 76 2.1 Unary Languages 77 3 Results 77 3.1 Intuition, Method of Proof and Main Results 77 3.2 A Regularity Condition by Decomposing into Unary Automata 80 3.3 The Special Case of Group Languages 83 4 Conclusion 86 References 87 Multiple Concatenation and State Complexity (Extended Abstract) 89 1 Introduction 89 2 Preliminaries 90 3 Construction of NFAs for Multiple Concatenation 91 4 Tightness for a (k+1)-letter Alphabet 93 5 Tightness for a k-letter Alphabet 96 6 Binary and Ternary Languages 98 7 Unary Cyclic Languages 99 8 Conclusions 100 References 101 Combining Limited Parallelism and Nondeterminism in Alternating Finite Automata 102 1 Introduction 102 2 Preliminaries 103 2.1 Tree Width of Alternating Machines 105 3 Decision Problems 109 4 Width Measure Bounds 112 References 113 Longer Shortest Strings in Two-Way Finite Automata 115 1 Introduction 115 2 Definitions 116 3 Shortest Strings in 2DFA 118 4 Iterating Semi-direction-determinate Automata 120 5 Encoding in a Fixed Alphabet 122 6 Automata with Longer Shortest Strings 124 7 Transforming Semi-direction-determinate to One-Way 125 8 Conclusion 125 References 126 Iterated Uniform Finite-State Transducers: Descriptional Complexity of Nondeterminism and Two-Way Motion 128 1 Introduction 128 2 Definitions and Preliminaries 130 3 Complexity of Mutual Nondeterministic Simulations 132 4 Costs of Simulations Involving Deterministic Devices 134 5 Iterated Transduction on Unary Languages 136 References 139 Descriptional Complexity of Winning Sets of Regular Languages 141 1 Introduction 141 2 Definitions 142 3 Winning Sets 143 4 Doubly Exponential Lower Bound 145 5 Case of the Bounded Regular Languages 148 6 Chain-Like Automata 149 7 Case Study: Exact Number of 1-Symbols 150 8 A Context-Free Language 151 References 152 State Complexity of GF(2)-inverse and GF(2)-star on Binary Languages 153 1 Introduction 153 2 GF(2)-star and GF(2)-inverse 155 3 Upper Bound for the GF(2)-inverse 156 4 Lower Bound for the GF(2)-inverse 158 5 Lower Bound for the GF(2)-star 163 6 Conclusion 164 References 164 Complexity of Two-Dimensional Rank-Reducing Grammars 166 1 Introduction 166 2 Preliminaries 167 3 Two-Dimensional Rank-Reducing Grammar 169 4 Parsing Complexity 170 5 Decidability and Descriptional Complexity 172 6 Conclusion 176 References 176 Palindromic Length of Words with Many Periodic Palindromes 178 1 Introduction 178 2 Preliminaries 180 3 Periodic Palindromic Factors 181 4 Palindromic Length of Concatenation 184 5 Concatenation of Periodic Palindromes 185 References 189 Operational Complexity of Straight Line Programs for Regular Languages 191 1 Introduction 191 2 Preliminaries 192 3 Lower Bound Techniques 194 4 SLP-Complexity of Operations 197 5 Complexity of Extended SLPs 199 6 Conclusion 202 References 202 Classifying -Regular Aperiodic k-Partitions 204 1 Introduction 204 2 Preliminaries 205 2.1 Aperiodic Acceptors and k-partitions 205 2.2 Aperiodic Transducers and Games 206 2.3 Semilattices and Labeled Posets 207 3 Classifying Aperiodic k-partitions 209 3.1 Reducibilities and Operations on k-partitions 209 3.2 The Fine Hierarchy of k-partitions 212 3.3 Computability and Complexity Issues 213 References 215 Recognition and Complexity Results for Projection Languages of Two-Dimensional Automata 217 1 Introduction 217 2 Preliminaries 218 2.1 Previous Work 219 3 Recognition Power and Space Complexity 220 3.1 Three-Way Two-Dimensional Automata 221 4 State Complexity 223 4.1 Union of 2NFA-2W Languages 223 4.2 Diagonal Concatenation of 2NFA-2W Languages 225 5 Conclusion 227 References 228 On the Generative Power of Quasiperiods 230 1 Introduction 230 2 Notation and Preliminaries 231 3 Quasiperiodic Words 231 3.1 Combinatorial Properties of Pq 231 3.2 The Reduced Quasiperiod 232 4 Asymptotic Growth 233 5 Polynomials 234 6 Irreducible Quasiperiods 235 6.1 Extremal Polynomials 235 6.2 The Ordering of the Maximal Roots n 236 7 Reducible Quasiperiods 238 7.1 The Case ||+|q0|2 238 7.2 The Case |q|-2|q0|3||+|q0|3 238 7.3 The Case |q|-2|q0|2|q0|+||3 239 References 241 Insertion-Deletion with Substitutions II 242 1 Introduction 242 2 Basic Definitions and Observations 242 3 Main Results 245 3.1 Extension with Context-Free Substitution 245 3.2 Extension with One-Sided Substitution 247 4 Conclusions 253 References 253 Author Index 255 Front Matter ....Pages i-x Mutually Accepting Capacitated Automata (Ravid Alon, Orna Kupferman)....Pages 1-12 Bad Pictures: Some Structural Properties Related to Overlaps (Marcella Anselmo, Dora Giammarresi, Maria Madonia, Carla Selmi)....Pages 13-25 Regular Expression Length via Arithmetic Formula Complexity (Ehud Cseresnyes, Hannes Seiwert)....Pages 26-38 Crisp-Determinization of Weighted Tree Automata over Additively Locally Finite and Past-Finite Monotonic Strong Bimonoids Is Decidable (Manfred Droste, Zoltán Fülöp, Dávid Kószó, Heiko Vogler)....Pages 39-51 On the Power of Generalized Forbidding Insertion-Deletion Systems (Henning Fernau, Lakshmanan Kuppusamy, Indhumathi Raman)....Pages 52-63 State Complexity Bounds for the Commutative Closure of Group Languages (Stefan Hoffmann)....Pages 64-77 Multiple Concatenation and State Complexity (Extended Abstract) (Jozef Jirásek, Galina Jirásková)....Pages 78-90 Combining Limited Parallelism and Nondeterminism in Alternating Finite Automata (Chris Keeler, Kai Salomaa)....Pages 91-103 Longer Shortest Strings in Two-Way Finite Automata (Stanislav Krymski, Alexander Okhotin)....Pages 104-116 Iterated Uniform Finite-State Transducers: Descriptional Complexity of Nondeterminism and Two-Way Motion (Martin Kutrib, Andreas Malcher, Carlo Mereghetti, Beatrice Palano)....Pages 117-129 Descriptional Complexity of Winning Sets of Regular Languages (Pierre Marcus, Ilkka Törmä)....Pages 130-141 State Complexity of GF(2)-inverse and GF(2)-star on Binary Languages (Alexander Okhotin, Elizaveta Sazhneva)....Pages 142-154 Complexity of Two-Dimensional Rank-Reducing Grammars (Daniel Průša)....Pages 155-166 Palindromic Length of Words with Many Periodic Palindromes (Josef Rukavicka)....Pages 167-179 Operational Complexity of Straight Line Programs for Regular Languages (Hannes Seiwert)....Pages 180-192 Classifying \(\omega \)-Regular Aperiodic k-Partitions (Victor Selivanov)....Pages 193-205 Recognition and Complexity Results for Projection Languages of Two-Dimensional Automata (Taylor J. Smith, Kai Salomaa)....Pages 206-218 On the Generative Power of Quasiperiods (Ludwig Staiger)....Pages 219-230 Insertion-Deletion with Substitutions II (Martin Vu, Henning Fernau)....Pages 231-243 Back Matter ....Pages 245-245