Published: 7th August 2010
DOI: 10.4204/EPTCS.31
ISSN: 2075-2180

EPTCS 31

Proceedings Twelfth Annual Workshop on
Descriptional Complexity of Formal Systems
Saskatoon, Canada, 8-10th August 2010

Edited by: Ian McQuillan and Giovanni Pighizzini

Preface
Ian McQuillan and Giovanni Pighizzini
Invited Presentation: On Formal Descriptions of Code Properties
Krystian Dudzinski and Stavros Konstantinidis
1
Invited Presentation: The Incompressibility Argument
Ming Li
2
Invited Presentation: L-systems in Geometric Modeling
Przemyslaw Prusinkiewicz, Mitra Shirmohammadi and Faramarz Samavati
3
Invited Presentation: Remembering Chandra Kintala
Martin Kappes, Andreas Malcher and Detlef Wotschke
15
On the Complexity of the Evaluation of Transient Extensions of Boolean Functions
Janusz Brzozowski, Baiyu Li and Yuli Ye
27
Finite-State Complexity and the Size of Transducers
Cristian Calude, Kai Salomaa and Tania Roblot
38
State Complexity of Testing Divisibility
Emilie Charlier, Narad Rampersad, Michel Rigo and Laurent Waxweiler
48
State Complexity of Catenation Combined with Star and Reversal
Bo Cui, Yuan Gao, Lila Kari and Sheng Yu
58
Accepting Hybrid Networks of Evolutionary Processors with Special Topologies and Small Communication
Jürgen Dassow and Florin Manea
68
Representing Small Ordinals by Finite Automata
Zoltan Ésik
78
Graph-Controlled Insertion-Deletion Systems
Rudolf Freund, Marian Kogler, Yurii Rogozhin and Sergey Verlan
88
Transition Complexity of Incomplete DFAs
Yuan Gao, Kai Salomaa and Sheng Yu
99
The Magic Number Problem for Subregular Language Families
Markus Holzer, Sebastian Jakobi and Martin Kutrib
110
Ciliate Gene Unscrambling with Fewer Templates
Lila Kari and Afroza Rahman
120
Descriptional Complexity of the Languages KaL: Automata, Monoids and Varieties
Ondřej Klíma and Libor Polák
130
State Elimination Ordering Strategies: Some Experimental Results
Nelma Moreira, Davide Nabais and Rogério Reis
139
Operational State Complexity of Deterministic Unranked Tree Automata
Xiaoxue Piao and Kai Salomaa
149
Transformations Between Different Types of Unranked Bottom-Up Tree Automata
Xiaoxue Piao and Kai Salomaa
159
The Maximal Subword Complexity of Quasiperiodic Infinite Words
Ronny Polley and Ludwig Staiger
169
On the Descriptional Complexity of Limited Propagating Lindenmayer Systems
Bianca Truthe
177
Nondeterministic State Complexity for Suffix-Free Regular Languages
Yo-Sub Han and Kai Salomaa
189
Complexity in Prefix-Free Regular Languages
Galina Jirásková and Monika Krausová
197
Learning Residual Finite-State Automata Using Observation Tables
Anna Kasprzik
205

Preface

Invited abstract

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

for accepting our invitation and presenting their recent results at DCFS 2010. Papers were submitted by a total of 50 authors from 14 different countries. From these submissions, on the basis of three referee reports each, the Program Committee selected 16 regular papers and 3 short papers. We thank the members of the Program Committee for their excellent work:

We also thank the additional reviewers for their careful evaluation:

We would like to thank EPTCS together with Rob van Glabbeek and Lane A. Hemaspaandra for their help in publishing these proceedings.

As in previous years, a special journal issue will be devoted to DCFS. Full versions of selected papers are eligible for publication in a special issue of the International Journal of Foundations of Computer Science (after the standard refereeing process).

We are grateful to the Organizing Committee consisting of Ian McQuillan (Chair), Wayne Clarke, Andrew Couperthwaite, Shakiba Jalal, Jillian Slind, and Brett Trost for their support of the sessions, the excursion and the other accompanying events.

We would finally like to thank all the participants for attending the DCFS workshop. We hope you can attend DCFS 2011 in Giessen, Germany.

Ian McQuillan and Giovanni Pighizzini

Saskatoon, Canada, August 2010

On Formal Descriptions of Code Properties

Krystian Dudzinski (Saint Mary's University)
Stavros Konstantinidis (Saint Mary's University)

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.

Our methodology can be viewed as a formal summarization of existing transducer-based techniques for deciding code properties, and provides uniform decision procedures for basic questions about code properties of languages. These include questions that have already been solved via other methodologies, as well as questions that had not been solved prior to this work.

The Incompressibility Argument

Ming Li (University of Waterloo)

Invited abstract

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.