Limit search to available items
Book Cover
E-book
Author DCFS (Workshop) (15th : 2013 : London, Ont.)

Title Descriptional complexity of formal systems : 15th International Workshop, DCFS 2013, London, ON, Canada, July 22-25, 2013. Proceedings / Helmut Jürgensen, Rogério Reis (eds.)
Published Heidelberg : Springer, [2013]

Copies

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
Other Titles DCFS 2013