Descriptional Complexity of Formal Systems

15th International Workshop, DCFS 2013, London, Canada, July 22-25, 2013, Proceedings

AvJürgensen,Rogério Reis

Häftad, Engelska, 2013

Del i serien Lecture Notes in Computer Science

534 kr

Beställningsvara. Skickas inom 10-15 vardagar. Fri frakt över 249 kr.

Beskrivning

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. size complexity and structural complexity of formal systems; size or structural complexity of formal systems for modeling natural languages;

Produktinformation

Utgivningsdatum:2013-07-19
Mått:155 x 235 x 17 mm
Vikt:458 g
Format:Häftad
Språk:Engelska
Serie:Lecture Notes in Computer Science
Antal sidor:289
Upplaga:2013
Förlag:Springer-Verlag Berlin and Heidelberg GmbH & Co. KG
ISBN:9783642393099

Utforska kategorier

Systemvetenskap och AI inom Data och IT
Programmeringsböcker inom Data och IT
Diskret matematik inom Naturvetenskap och teknik

Innehållsförteckning

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.