Descriptional Complexity of Formal Systems -

. .

Résumé :
This book constitutes the refereed proceedings of the 15th International Workshop of Descriptional Complexity of Formal Systems, DCFS 2013, held in London, ON, Canada, in July 2013. The 22 revised full papers presented together with 4 invited papers were carefully reviewed and selected from 46 submissions. The topics covered are automata, grammars, languages and other formal systems; various modes of operations and complexity measures; co-operating systems; succinctness of description of objects, state-explosion-like phenomena; circuit complexity of Boolean functions and related measures; size complexity and structural complexity of formal systems; trade-offs between computational models and mode of operation; applications of formal systems; for instance in software and hardware testing, in dialogue systems, in systems modeling or in modeling natural languages; and their complexity constraints; size or structural complexity of formal systems for modeling natural languages; complexity aspects related to the combinatorics of words; descriptional complexity in resource-bounded or structure-bounded environments; structural complexity as related to descriptional complexity; frontiers between decidability and undecidability; universality and reversibility; nature-motivated (bio-inspired) architectures and unconventional models of computing; Kolmogorov-Chaitin complexity, algorithmic information.

Sommaire:

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.