Buch, Englisch, Band 8031, 289 Seiten, Format (B × H): 155 mm x 235 mm, Gewicht: 458 g
15th International Workshop, DCFS 2013, London, Canada, July 22-25, 2013, Proceedings
Buch, Englisch, Band 8031, 289 Seiten, Format (B × H): 155 mm x 235 mm, Gewicht: 458 g
Reihe: Lecture Notes in Computer Science
ISBN: 978-3-642-39309-9
Verlag: Springer
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.
Zielgruppe
Research
Autoren/Hrsg.
Fachgebiete
Weitere Infos & Material
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.