Language and Automata Theory and Applications: 14th International Conference, LATA 2020, Milan, Italy, March 4–6, 2020, Proceedings (Theoretical Computer Science and General Issues)

This book constitutes the proceedings of the 14th International Conference on Language and Automata Theory and Applications, LATA 2020, which was planned to be held in Milan, Italy, in March 2020. Due to the corona pandemic, the actual conference was postponed and will be held together with LATA 2021. The 26 full papers presented in this volume were carefully reviewed and selected from 59 submissions. They were organized in topical sections named: algebraic structures; automata; complexity; grammars; languages; trees and graphs; and words and codes. The book also contains 6 invited papers in full-paper length. Preface Organization Contents Invited Papers The New Complexity Landscape Around Circuit Minimization 1 Introduction 2 Meta-complexity, MCSP and Kolmogorov Complexity 3 Connections to Learning Theory 4 Completeness, Hardness, Reducibility 4.1 Completeness in EXP and Other Classes 4.2 NP-Hardness 5 Average Case Complexity, One-Way Functions 6 Complexity Classes and Noncomputable Complexity Measures 7 Magnification References Containment and Equivalence of Weighted Automata: Probabilistic and Max-Plus Cases 1 Introduction 2 Weighted Automata 2.1 Preliminaries 2.2 Graphical Definition 2.3 Matrix Representation 2.4 Classic Examples 3 Decision Problems 3.1 The Equivalence and Containment Problems 3.2 Undecidability of the Containment Problem 3.3 Equivalence 3.4 Decidability: Restricting the Ambiguity 4 Approximations 4.1 Probabilistic Case 4.2 Approximating Max-Plus and Min-Plus Automata 5 Conclusion References Approaching Arithmetic Theories with Finite-State Automata 1 Introduction 2 Preliminaries 2.1 Büchi Arithmetic 2.2 Finite-State Automata and p-automata 2.3 Semi-linear Sets 3 Existential Büchi Arithmetic 4 Presburger Arithmetic with Valuation Constraints 5 Conclusion References Recompression: Technique for Word Equations and Compressed Data 1 Introduction 1.1 Word Equations 1.2 Compression and Word Equations 1.3 Recompression 1.4 Algorithms for Grammar-Based Compression 2 Recompression for Word Equations 3 Extensions of the Algorithm for Word Equations 3.1 O(n logn) Space 3.2 Equations with Regular Constraints and Inversion; Equations in Free Groups 3.3 Context Unification 4 Recompression and Compressed Data 4.1 Straight Line Programs and Recompression 4.2 SLP Equality and Fully Compressed Pattern Matching References How to Prove that a Language Is Regular or Star-Free? 1 Background 1.1 Regular and Star-Free Languages 1.2 Early Results and Their Consequences 1.3 Recognition by a Monoid and Syntactic Monoid 2 Iteration Properties 2.1 Pumping 2.2 Periodicity and Permutation 2.3 Iteration Properties 3 Rewriting Systems and Well Quasi-orders 3.1 Rewriting Systems 3.2 Suffix Rewriting Systems 3.3 Deleting Rewriting Systems 3.4 Rules of the Form un to um 3.5 Well Quasi-orders 3.6 Equations and Inequalities 4 Logic 4.1 Logic on Words 4.2 Linear Temporal Logic 4.3 Rabin's Tree Theorem 5 Transductions 5.1 Rational and Recognisable Sets 5.2 Matrix Representations of Transductions 5.3 Decompositions of Languages 6 Profinite Topology 6.1 Uniformly Continuous Functions and Recognisable sets 6.2 Transductions and Recognisable Sets 7 Further Examples and Conclusion References Deciding Classes of Regular Languages: The Covering Approach 1 Introduction 2 Preliminaries 3 The Covering Problem 3.1 Definition 3.2 Application to Membership 4 Star-Free Languages and Schützenberger's Theorem 4.1 Definition 4.2 Schützenberger's Theorem 5 Piecewise Testable Languages and Simon's Theorem 5.1 Definition 5.2 Simon's Theorem 6 Conclusion References Algebraic Structures Nonstandard Cayley Automatic Representations for Fundamental Groups of Torus Bundles over the Circle 1 Introduction and Preliminaries 2 Nies–Semukhin FA–Presentations of (Zn,+) 3 FA–Recognizable Automorphisms of Zn 4 Conclusion and Open Questions References "426830A R, +,