Intro
Preface
Organization
Contents
Mutually Accepting Capacitated Automata
1 Introduction
2 Preliminaries
3 Expressive Power
3.1 Regularity
3.2 Determinism
3.3 Closure Properties
4 Decision Problems
References
Bad Pictures: Some Structural Properties Related to Overlaps
1 Introduction
2 Preliminaries
2.1 Basic Notions and Results on Strings
2.2 Basic Notions on Pictures
3 Good and Bad Pictures
4 Index of Bad Pictures
References
Regular Expression Length via Arithmetic Formula Complexity
1 Introduction
2 Preliminaries

3 Reduction to Monotone Arithmetic Formula Size
3.1 Bounds for Uniform Languages
3.2 Blow-Up of Language Operations
3.3 Limitations of the Arithmetic Bound
4 Direct Lower Bounds
4.1 The Divisibility Language
4.2 Utilizing Noncommutativity
5 Conclusion
References
Crisp-Determinization of Weighted Tree Automata over Additively Locally Finite and Past-Finite Monotonic Strong Bimonoids Is Decidable
1 Introduction
2 Preliminaries
2.1 General Notions and Notations
2.2 Trees and Contexts
2.3 Strong Bimonoids
3 Weighted Tree Automata with Run Semantics

4 Pumping Lemma
5 Main Result
References
On the Power of Generalized Forbidding Insertion-Deletion Systems
1 Introduction
2 Important Definitions
3 Main Results
4 Conclusions
References
State Complexity Bounds for the Commutative Closure of Group Languages
1 Introduction
2 Prerequisites
2.1 Unary Languages
3 Results
3.1 Intuition, Method of Proof and Main Results
3.2 A Regularity Condition by Decomposing into Unary Automata
3.3 The Special Case of Group Languages
4 Conclusion
References

Multiple Concatenation and State Complexity (Extended Abstract)
1 Introduction
2 Preliminaries
3 Construction of NFAs for Multiple Concatenation
4 Tightness for a (k+1)-letter Alphabet
5 Tightness for a k-letter Alphabet
6 Binary and Ternary Languages
7 Unary Cyclic Languages
8 Conclusions
References
Combining Limited Parallelism and Nondeterminism in Alternating Finite Automata
1 Introduction
2 Preliminaries
2.1 Tree Width of Alternating Machines
3 Decision Problems
4 Width Measure Bounds
References

Longer Shortest Strings in Two-Way Finite Automata
1 Introduction
2 Definitions
3 Shortest Strings in 2DFA
4 Iterating Semi-direction-determinate Automata
5 Encoding in a Fixed Alphabet
6 Automata with Longer Shortest Strings
7 Transforming Semi-direction-determinate to One-Way
8 Conclusion
References
Iterated Uniform Finite-State Transducers: Descriptional Complexity of Nondeterminism and Two-Way Motion
1 Introduction
2 Definitions and Preliminaries
3 Complexity of Mutual Nondeterministic Simulations
4 Costs of Simulations Involving Deterministic Devices