Descriptional Complexity of Formal Systems

16th International Workshop, DCFS 2014, Turku, Finland, August 5-8, 2014, Proceedings

Helmut Jürgensen, Juhani Karhumäki, Alexander Okhotin (Herausgeber)

Buch | Softcover

XII, 366 Seiten

2014
Springer International Publishing (Verlag)
978-3-319-09703-9 (ISBN)

Artikel merken

This book constitutes the refereed proceedings of the 16th International Conference on Descriptional Complexity of Formal Systems, DCFS 2014, held in Turku, Finland, in August 2014. The 27 full papers presented were carefully reviewed and selected from 35 submissions. The conference dealt with the following topics: Automata, grammars, languages and other formal systems; various modes of operation and complexity measures; trade-offs between computational models and modes of operation; succinctness of description of objects, state explosion-like phenomena; circuit complexity of Boolean functions and related measures; resource-bounded or structure-bounded environments; frontiers between decidability and undecidability; universality and reversibility; structural complexity; formal systems for applications (e.g., software reliability, software and hardware testing, modeling of natural languages); nature-motivated (bio-inspired) architectures and unconventional models of computing; complexity aspects of combinatorics on words; Kolmogorov complexity.

Automata, grammars, languages and other formal systems.- Various modes of operation and complexity measures.- Trade-offs between computational models and modes of operation.- Succinctness of description of objects, state explosion-like phenomena.- Circuit complexity of Boolean functions and related measures.- Resource-bounded or structure-bounded environments.- Frontiers between decidability and undecidability.- Universality and reversibility.- Structural complexity.- Formal systems for applications (e.g., software reliability, software and hardware testing, modeling of natural languages).- Nature-motivated (bio-inspired) architectures and unconventional models of computing.- Complexity aspects of combinatorics on words.- Kolmogorov complexity.

Erscheint lt. Verlag	21.7.2014
Reihe/Serie	Lecture Notes in Computer Science
Reihe/Serie	Theoretical Computer Science and General Issues
Zusatzinfo	XII, 366 p. 59 illus.
Verlagsort	Cham
Sprache	englisch
Maße	155 x 235 mm
Gewicht	581 g
Themenwelt	Informatik ► Software Entwicklung ► User Interfaces (HCI)
	Informatik ► Theorie / Studium ► Algorithmen
	Mathematik / Informatik ► Mathematik
Schlagworte	Algorithm analysis and problem complexity • context-free languages • Error-correcting codes • Quantum Computation • regular languages • Turing Machines
ISBN-10	3-319-09703-2 / 3319097032
ISBN-13	978-3-319-09703-9 / 9783319097039
Zustand	Neuware