Preface

Descriptional Complexity of Formal Systems (DCFS) is the successor workshop and the merger of two related workshops, Descriptional Complexity of Automata, Grammars and Related Structures (DCAGRS) and Formal Descriptions and Software Reliability (FDSR). The DCAGRS workshop took place in Magdeburg, Germany (1999), London, Ontario, Canada (2000), and Vienna, Austria (2001), while the FDSR workshop took place in Paderborn, Germany (1998), Boca Raton, Florida, USA (1999), and San Jose, California, USA (2000). The DCFS workshop has previously been held in London, Ontario, Canada (2002), Budapest, Hungary (2003), London, Ontario, Canada (2004), Como, Italy (2005), Las Cruces, New Mexico, USA (2006), Nový Smokovec, Slovakia (2007), Charlottetown, Prince Edward Island, Canada (2008), and Magdeburg, Germany (2009).

Descriptional Complexity of Formal Systems 2010 is the 12th annual edition of the workshop, and it is taking place in Saskatoon, Canada, on August 8-10, 2010. It was jointly organized by the IFIP Working Group 1.2 on Descriptional Complexity and by the Department of Computer Science at the University of Saskatchewan in Saskatoon, Canada.

This volume contains the papers of the invited lectures and the accepted contributions. The workshop has a long history of being a scientifically valuable and important event for theoretical computer science. We hope that this year's workshop will stimulate new investigations and scientific co-operation in the field of descriptional complexity.

Special thanks go to the invited speakers

• Stavros Konstantinidis, Saint Mary's University, Canada
• Ming Li, University of Waterloo, Canada
• Przemyslaw Prusinkiewicz, University of Calgary, Canada
• Detlef Wotschke, Frankfurt, Germany; Giessen University, Germany

• Janusz A. (John) Brzozowski (Waterloo, ON, Canada)
• Jürgen Dassow (Magdeburg, Germany)
• Michael Domaratzki (Winnipeg, MB, Canada)
• Markus Holzer (Giessen, Germany)
• Oscar H. Ibarra (Santa Barbara, CA, USA)
• Galina Jirásková (Kosice, Slovakia)
• Chandra Kintala (Newark, USA)
• Ian McQuillan (Saskatoon, SK, Canada, co-chair)
• Andrei Paun (Madrid, Spain; Bucharest, Romania)
• Giovanni Pighizzini (Milano, Italy, co-chair)
• Jacques Sakarovitch (Paris, France)
• Kai Salomaa (Kingston, ON, Canada)
• György Vaszil (Hungarian Academy of Sciences, Budapest, Hungary)
• Sheng Yu (London, ON, Canada)

• Petr Ambrož
• Nicolas Bedon
• Cezar Câmpeanu
• Bo Cui
• Henning Fernau
• Viliam Geffert
• Yo-Sub Han
• Sebastian Jakobi
• Martin Kutrib
• Markus Lohrey
• Maurice Margenstern
• Tomáš Masopust
• Carlo Mereghetti
• Eva Miliczká
• Joachim Niehren
• Alexander Okhotin
• Xiaoxue Piao
• Jean-Éric Pin
• Shinnosuke Seki
• Jeffrey Shallit
• Pedro V. Silva
• Benjamin Steinberg
• Klaus Sutner
• Alexander Szabari

On Formal Descriptions of Code Properties

The branch of coding theory that is based on automata and formal languages has matured to a point that allows one to express mathematically a wide variety of code properties - pertaining, for instance, to data communications and DNA computing. In particular, several methodologies now exist for defining code properties. These methodologies include partial word orders, dependence systems, implicational conditions, language inequations, and trajectory sets. Of those, the latter three can be viewed as formal description methods of code properties in the sense that a certain formal object is used to define a code property (such as the property of a code being prefix, infix, error-detecting). For example, in the case of trajectory sets, a regular expression E over the binary alphabet defines a code property via a condition that involves the shuffle operation on the trajectory set defined by E and any language L such that the desired code property is exactly the set of all languages L satisfying the condition. Depending on the choice of the regular expression E, one can define, for instance, the class of infix codes. In the case of implicational conditions, a certain type of a first order formula F that involves a variable L, defines a code property in the sense that F is satisfied exactly when L has the desired property.

In this work we present a methodology for describing code properties that is based on transducers. Each transducer of a certain type defines a desired property. In doing so, we have the following objectives in mind.

• To be compatible and more general (when possible) with other existing methodologies.
• To be able to decide, given the descriptions of a code property P and a regular language L, whether L has the property P.
• To be able to decide, given the descriptions of a code property P and a regular language L, whether L is maximal with the property P.
• To be able to build a web language server that allows a user to enter descriptions of code properties and produce answers to questions about languages with the desired code properties.

The Incompressibility Argument

Inputs that do not have short descriptions are typical. A single such typical input can be used to obtain the average-case complexity of an algorithm. Recent developments show that this method not only works for high probability events such as in the average-case analysis, but also it works for low probability events such as in the constructive proof of Lovasz local lemma. This talk will describe this incompressibility argument via several simple examples.