14th International Workshop on Descriptional Complexity of Formal Systems

Braga 23.-25.7.2012

DCFS 2012, Descriptional Complexity of Formal Systems, will be held in Braga, Portugal on July 23-25, 2012 and will be jointly organized by University of Porto and University of Minho with the support of University of Beira Interior. DCFS 2012 will take place just after CIAA 2012


Submissions concerning the descriptional complexity of formal systems and structures (and its applications) are invited for DCFS 2012. Topics related to all aspects of descriptional complexity, including, but not limited to

  • automata, grammars, languages and related systems, various measures and modes of operations (e.g., determinism and nondeterminism),
  • trade-offs between computational models and/or operations,
  • succinctness of description of (finite) 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, modelling of natural languages),
  • nature-motivated (bio-inspired) architectures and unconventional models of computing,
  • Kolmogorov complexity.

The proceedings will be published in the Springer Lecture Notes in Computer Science (LNCS) series. As in previous years, a special journal issue with full versions of selected papers will be devoted to DCFS 2012.

Selected publications

2012MEDUNA Alexander, VRÁBEL Lukáš and ZEMEK Petr. An Infinite Hierarchy of Language Families Resulting from Stateless Pushdown Automata with Limited Pushdown Alphabets. In: DCFS'12: 14th International Workshop on Descriptional Complexity of Formal Systems. Braga: Springer Verlag, 2012, pp. 236-243. ISBN 978-3-642-31622-7. ISSN 0302-9743.

Your IPv4 address:
Switch to https

DNSSEC [dnssec]