Descriptional Complexity of Formal Systems: 15th International Workshop, DCFS 2013, London, Canada, July 22-25, 2013, Proceedings - Softcover

Softcover

ISBN 10: 364239311X ISBN 13: 9783642393112

Publisher: Springer, 2013

Synopsis

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.

Edition details

• Publisher: Springer
• Publication date: 2013
• Language: English
• ISBN 10: 364239311X
• ISBN 13: 9783642393112
• Binding: Paperback