Descriptional Complexity of Formal Systems

Blum Static Complexity and Encoding Spaces.- Millstream Systems and Graph Transformation for Complex Linguistic Models.- Can Chimps Go It Alone.- Invertible Transductions and Iteration.- Universal Witnesses for State Complexity of Boolean Operations and Concatenation Combined with Star.- Searching for Traces of Communication in Szilard Languages of Parallel Communicating Grammar Systems - Complexity Views.- State Complexity of Basic Operations on Non-returning Regular Languages.- State Complexity of Subtree-Free Regular Tree Languages.- State Complexity of k -Union and k -Intersection for Prefix-Free Regular Languages.- A Direct Construction of Finite State Automata for Pushdown Store Languages.- Nondeterministic State Complexity of Proportional Removals.- Nondeterministic Biautomata and Their Descriptional Complexity.- Queue Automata of Constant Length.- On the State Complexity of the Reverse of R - and J -Trivial Regular Languages.- Size of Unary One-Way Multi-head Finite Automata.- Syntactic Complexity of R - and J -Trivial Regular Languages.- Sophistication as Randomness Deficiency.- Shortest Repetition-Free Words Accepted by Automata.- A Characterisation of NL /poly via Nondeterministic Finite Automata.- Improved Normal Form for Grammars with One-Sided Contexts.- Comparisons between Measures of Nondeterminism on Finite Automata.- Finite Nondeterminism vs. DFAs with Multiple Initial States.- The Power of Centralized PC Systems of Pushdown Automata.- Limited Automata and Regular Languages.- Reversal on Regular Languages and Descriptional Complexity.- Kleene Star on Unary Regular Languages.