Descriptional Complexity of Formal Systems
Springer Berlin (Verlag)
978-3-642-39309-9 (ISBN)
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.
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.
| Erscheint lt. Verlag | 19.7.2013 |
|---|---|
| Reihe/Serie | Lecture Notes in Computer Science | Theoretical Computer Science and General Issues |
| Zusatzinfo | X, 289 p. 56 illus. |
| Verlagsort | Berlin |
| Sprache | englisch |
| Maße | 155 x 235 mm |
| Gewicht | 456 g |
| Themenwelt | Informatik ► Software Entwicklung ► User Interfaces (HCI) |
| Informatik ► Theorie / Studium ► Algorithmen | |
| Mathematik / Informatik ► Mathematik | |
| Schlagworte | Algorithm analysis and problem complexity • context-free languages • descriptional complexity • Finite Automata • Regular Expressions • Turing Machines |
| ISBN-10 | 3-642-39309-8 / 3642393098 |
| ISBN-13 | 978-3-642-39309-9 / 9783642393099 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
