Descriptional Complexity of Formal Systems: 24th IFIP WG 1.02 International Conference, DCFS 2022, Debrecen, Hungary, August 29–31, 2022, Proceedings (Lecture Notes in Computer Science, 13439)

This book constitutes the proceedings of the 24th International Conference on Descriptional Complexity of Format Systems, DCFS 2022, which was supposed to take place in Debrecen, Hungary in August 2022. The 14 full papers presented in this volume were carefully reviewed and selected from 17 submissions. The book also contains 4 invited talks. The conference focus to all aspects of descriptional complexity including Automata, grammars, languages, and other formal systems; various modes of operations and complexity measures. Preface Organization Abstracts of Invited Talks Polyregular Functions On Scattered Context-free Order Types (Extended Abstract) Operations on Unambiguous Finite Automata (Extended Abstract) Contents The Alphabetic Complexity in Homomorphic Definitions of Word, Tree and Picture Languages 1 Introduction 2 Basic Definitions and Properties 2.1 Regular and Strictly Locally Testable Word Languages 2.2 Comma-Free Codes 3 The Extended Medvedev's Theorem for Words 4 The Extended Medvedev's Theorem for Trees and Pictures 4.1 Tree Languages 4.2 Picture Languages 5 Conclusion References Ranking Binary Unlabelled Necklaces in Polynomial Time 1 Introduction 2 Preliminaries 2.1 Unlabelled Necklaces 2.2 Bounding Subwords 3 Ranking 4 Symmetric Necklaces 5 Enclosing Necklaces References On the Power of Recursive Word-Functions Without Concatenation 1 Introduction 2 Definitions 3 First Constructions 3.1 Word Manipulations 3.2 Logical Functions 3.3 Encoding and Pairing 4 Primitive Recursion Without Concatenation 4.1 Some Algebraic Languages Decided in 4.2 Some Non-algebraic Languages Decided in 5 Regular Languages are Decidable in with Multiple Recursion 6 Conclusion References Clusters of Repetition Roots Forming Prefix Chains 1 Introduction 2 Preliminaries 2.1 Clusters of Repetition Roots 3 Single Chains 3.1 Optimality 3.2 Single Chains of Run Ending Squares 4 Two Overlapping Chains References Nearly k-Universal Words - Investigating a Part of Simon's Congruence 1 Introduction 2 Preliminaries 3 Nearly k-Universal Words 4 m-Nearly k-Universal Words 5 Conclusion References State Complexity of Binary Coded Regular Languages 1 Introduction 2 Preliminaries 3 Upper and Lower Bounds 4 The Hierarchy 5 Concluding Remarks References Reset Complexity and Completely Reachable Automata with Simple Idempotents 1 Introduction 2 Some More Notation and Preliminary Results 3 Completely Reachable Automata 4 The Structure of Sync-Maximal Automata 5 Automata with Simple Idempotents 6 Conclusion References On the Descriptional Complexity of the Direct Product of Finite Automata 1 Introduction 2 Preliminaries 3 Results References Operations on Subregular Languages and Nondeterministic State Complexity 1 Introduction 2 Preliminaries 3 Results 4 Conclusions References On Simon's Congruence Closure of a String 1 Introduction 2 Preliminaries 3 Main Contributions 3.1 Vectors and Blocks 3.2 DFA Construction 3.3 State Complexity for Closurek(w) 4 Conclusions References Approximate NFA Universality Motivated by Information Theory 1 Introduction 2 Basic Notation and Background Information 3 Randomized Approximation of [0, 1]-Value Problems 4 Word Distributions 5 Universality Index of NFAs 6 Randomized Approximation of NFA Problems Relative to Uniform Distributions 7 Randomized Approximation of NFA Universality 8 Concluding Remarks References Lazy Regular Sensing 1 Introduction 2 Defining Lazy Sensing 2.1 Deterministic Finite Automata 2.2 Potentially Sensed Signals 2.3 Sensing Trees 2.4 The Sensing Cost of a Sensing Tree 2.5 Static vs. Dynamic Sensing Trees 2.6 The Sensing Cost of a DFA and a Regular Language 3 Probability-Based Definition of Lazy-Sensing Cost 4 Lazy-Sensing Cost vs. Size 5 Comparing the Different Sensing Classes 5.1 Lazy vs. Naive Sensing 5.2 Comparison of the Different Lazy-Sensing Classes 6 Directions for Future Research References State Complexity of Finite Partial Languages 1 Introduction 2 Preliminaries 3 State Trade-Offs Between Nondeterminism, Partial Words, and Determinism 3.1 State Complexity of the NFA to -DFA Conversion 3.2 State Complexity of the -DFA to DFA Conversion 4 Operational State Complexity 5 Hierarchy of -Transitions 6 Conclusion References Yet Another Canonical Nondeterministic Automaton 1 Introduction 2 Automata, Quotients, and Atoms of Regular Languages 3 Residual Finite State Automata 4 Maximized Átomaton 5 Maximized Prime Átomaton 6 Observation Tables 6.1 Row Automaton 6.2 Column Automaton 6.3 Rows and Columns 6.4 Primes 6.5 Prime Row Automaton 6.6 Prime Column Automaton 6.7 Learning NFAs 7 Conclusions References Union-Complexities of Kleene Plus Operation 1 Introduction 2 Preliminaries 3 Operational Union-Complexity of the Kleene Plus Operation 3.1 On n-Union-Complexity 3.2 On Deterministic Union-Complexity References Author Index