Descriptional complexity of formal systems : 19th IFIP WG 1.02 international conference, DCFS 2017, Milano, ITaly, July 3-5, 2017 : proceedings

This book constitutes the proceedings of the 19th International Conference on Descriptional Complexity of Formal Systems, DCFS 2017, held in Milano, Italy, in July 2017. The 20 full papers presented together with 4 invited talks were carefully reviewed and selected from 26 submissions.Descriptional Complexity is a field in Computer Science that deals with the size of all kinds of objects that occur in computational models, such as turing machines, finite automata, grammars, splicing systems and others. The topics of this conference are related to all aspects of descriptional complexity. Front Matter....Pages I-X Front Matter....Pages 1-1 Sensing as a Complexity Measure....Pages 3-15 Avoiding Overlaps in Pictures....Pages 16-32 Descriptional Complexity and Operations – Two Non-classical Cases....Pages 33-44 Applications of Transducers in Independent Languages, Word Distances, Codes....Pages 45-62 Front Matter....Pages 63-63 On the Degree of Nondeterminism of Tree Adjoining Languages and Head Grammar Languages....Pages 65-76 On the Average Complexity of Strong Star Normal Form....Pages 77-88 Most Complex Non-returning Regular Languages....Pages 89-101 Uncountable Realtime Probabilistic Classes....Pages 102-113 A Parametrized Analysis of Algorithms on Hierarchical Graphs....Pages 114-127 Graph-Controlled Insertion-Deletion Systems Generating Language Classes Beyond Linearity....Pages 128-139 Computational Completeness of Networks of Evolutionary Processors with Elementary Polarizations and a Small Number of Processors....Pages 140-151 Recognizing Union-Find Trees Built Up Using Union-By-Rank Strategy is NP-Complete....Pages 152-163 Self-attraction Removal from Oritatami Systems....Pages 164-176 One-Time Nondeterministic Computations....Pages 177-188 Kuratowski Algebras Generated by Factor-, Subword-, and Suffix-Free Languages....Pages 189-201 Branching Measures and Nearly Acyclic NFAs....Pages 202-213 Square on Deterministic, Alternating, and Boolean Finite Automata....Pages 214-225 A Pumping Lemma for Ordered Restarting Automata....Pages 226-237 Concise Representations of Reversible Automata....Pages 238-249 State Complexity of Unary SV-XNFA with Different Acceptance Conditions....Pages 250-261 Front Matter....Pages 63-63 Reset Complexity of Ideal Languages Over a Binary Alphabet....Pages 262-273 2-State 2-Symbol Turing Machines with Periodic Support Produce Regular Sets....Pages 274-286 State Complexity of Suffix Distance....Pages 287-298 The Quotient Operation on Input-Driven Pushdown Automata....Pages 299-310 Back Matter....Pages 311-311