Description |
1 online resource (x, 288 pages) : illustrations (black and white) |
Series |
Lecture notes in computer science, 0302-9743 ; 8031 |
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues |
|
Lecture notes in computer science ; 8031.
|
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues.
|
Contents |
Blum Static Complexity and Encoding Spaces / Cezar Câmpeanu -- Millstream Systems and Graph Transformation for Complex Linguistic Models / Frank Drewes -- Can Chimps Go It Alone? / Pierre McKenzie -- Invertible Transductions and Iteration / Klaus Sutner -- Universal Witnesses for State Complexity of Boolean Operations and Concatenation Combined with Star / Janusz Brzozowski, David Liu -- Searching for Traces of Communication in Szilard Languages of Parallel Communicating Grammar Systems -- Complexity Views / Liliana Cojocaru, Erkki Mäkinen -- State Complexity of Basic Operations on Non-returning Regular Languages / Hae-Sung Eom, Yo-Sub Han, Galina Jirásková -- State Complexity of Subtree-Free Regular Tree Languages / Hae-Sung Eom, Yo-Sub Han, Sang-Ki Ko -- State Complexity of k-Union and k-Intersection for Prefix-Free Regular Languages / Hae-Sung Eom, Yo-Sub Han, Kai Salomaa -- A Direct Construction of Finite State Automata for Pushdown Store Languages / Viliam Geffert, Andreas Malcher, Katja Meckel -- Nondeterministic State Complexity of Proportional Removals / Daniel Goč, Alexandros Palioudakis -- Nondeterministic Biautomata and Their Descriptional Complexity / Markus Holzer, Sebastian Jakobi -- Queue Automata of Constant Length / Sebastian Jakobi, Katja Meckel -- On the State Complexity of the Reverse of R -- and J -Trivial Regular Languages / Galina Jirásková, Tomáš Masopust -- Size of Unary One-Way Multi-head Finite Automata / Martin Kutrib, Andreas Malcher -- Syntactic Complexity of R -- and J -Trivial Regular Languages / Janusz Brzozowski, Baiyu Li -- Sophistication as Randomness Deficiency / Francisco Mota, Scott Aaronson, Luís Antunes -- Shortest Repetition-Free Words Accepted by Automata / Hamoon Mousavi, Jeffrey Shallit -- A Characterisation of NL/poly via Nondeterministic Finite Automata / Rob Myers, Henning Urbat -- Improved Normal Form for Grammars with One-Sided Contexts / Alexander Okhotin -- Comparisons between Measures of Nondeterminism on Finite Automata / Alexandros Palioudakis, Kai Salomaa -- Finite Nondeterminism vs. DFAs with Multiple Initial States / Alexandros Palioudakis, Kai Salomaa -- The Power of Centralized PC Systems of Pushdown Automata / Holger Petersen -- Limited Automata and Regular Languages / Giovanni Pighizzini, Andrea Pisoni -- Reversal on Regular Languages and Descriptional Complexity / Juraj Šebej -- Kleene Star on Unary Regular Languages / Kristína Čevorová |
Summary |
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 |
Analysis |
Computer science |
|
Computer software |
|
Logic design |
|
Computational complexity |
|
Computation by Abstract Devices |
|
Mathematical Logic and Formal Languages |
|
Logics and Meanings of Programs |
|
Algorithm Analysis and Problem Complexity |
|
Discrete Mathematics in Computer Science |
|
computerwetenschappen |
|
computer sciences |
|
wiskunde |
|
mathematics |
|
algoritmen |
|
algorithms |
|
computeranalyse |
|
computer analysis |
|
logica |
|
logic |
|
computational science |
|
Information and Communication Technology (General) |
|
Informatie- en communicatietechnologie (algemeen) |
Notes |
International conference proceedings |
|
Includes author index |
Bibliography |
Includes bibliographical references and author index |
Subject |
Formal methods (Computer science) -- Congresses
|
|
Formal languages -- Congresses
|
|
Programming languages (Electronic computers)
|
|
Programming Languages
|
|
Programming languages (Electronic computers)
|
|
Formal languages
|
|
Formal methods (Computer science)
|
Genre/Form |
proceedings (reports)
|
|
Conference papers and proceedings
|
|
Conference papers and proceedings.
|
|
Actes de congrès.
|
Form |
Electronic book
|
Author |
Jürgensen, Helmut, editor
|
|
Reis, Rogério (Cryptographer), editor.
|
ISBN |
9783642393105 |
|
3642393101 |
|
3642393098 |
|
9783642393099 |
|