Invited Speakers

Rudolf Freund (TU Wien, Austria)

A General Framework for Sequential Grammars with Control Mechanisms

Since more than five decades, many control mechanisms have been introduced for sequential string grammars, including control graphs, matrices, permitting and forbidden contexts, and order relations. These control mechanisms then have been extended to sequential grammars working on objects different from strings, for example, to array, graph, and multiset grammars. Many relations between the languages generated by sequential grammars working with on these objects with different control mechanisms were shown to be similar to the relations already proved for the string case. Within a general framework for regulated rewriting based on the applicability of rules in sequential grammars, many relations between various control mechanisms can be established in a very general setting without any reference to the underlying objects the rules are working on; besides the well-known control mechanisms as control graphs, matrices, permitting and forbidden rules, partial order on rules, and priority relations on rules, the new variants of activation of rules as well as activation and blocking of rules are considered. Special results for strings and multisets as well as for arrays in the general variant defined on Cayley grids of finitely presented groups are exhibited based on the general results. Finally, some general results for cooperating distributed grammar systems are established.

Jarkko Kari (University of Turku, Finland)

Low-Complexity Tilings of the Plane

A two-dimensional configuration is a coloring of the infinite grid Z² by finitely many distinct colors. For a finite subset D of Z², the D-patterns of a configuration are the patterns of shape D that appear in the configuration. The number of distinct D-patterns of a configuration is a natural measure of its complexity. We consider low-complexity configurations where the number of distinct D-patterns is at most |D|, the size of the shape. We use algebraic tools to study periodicity of such configurations. In the case D is a rectangle, we prove that any subshift containing the configuration also contains a periodic configuration. This implies an algorithm to determine if a given |mn| patterns of rectangular shape m times n admit a configuration containing only these patterns. (Without the complexity bound the question is the well-known undecidable domino problem.) We also show, for an arbitrary shape D, that a low-complexity configuration must be periodic if it comes from the well-known Ledrappier subshift, or from a wide family of other similar algebraic subshifts.

Benedek Nagy (Eastern Mediterranean University, Northern Cyprus)

Union-Freeness, Deterministic Union-Freeness and Union Complexity

Union-free expressions are regular expressions without using the union operation. Consequently, union-free languages are described by regular expressions using only concatenation and Kleene star. The language class is also characterised by a special class of finite automata: 1CFPAs have exactly one cycle-free accepting path from each of their states. Obviously such an automaton has exactly one accepting state. The deterministic counterpart of such class of automata defines the deterministic union-free languages. A regular expression is in union (disjunctive) normal form if it is a finite union of union-free expressions. By manipulating regular expressions, each of them has equivalent expression in union normal form. By the minimum number of union-free expressions needed to describe a regular language, its union complexity is defined. For any natural number n there are languages such that their union complexity is n. However, there is not known any simple algorithm to determine the union complexity of any language. Regarding the deterministic union-free languages, there are regular languages such that they cannot be written as a union of finitely many deterministic union-free languages.

Giovanni Pighizzini (University of Milan, Italy)

Limited Automata: Properties, Complexity and Variants

Limited automata are single-tape Turing machines with severe rewriting restrictions. In a work of 1967 Thomas Hibbard, who introduced them, proved that they have the same computational power as pushdown automata. Hence, they provide an alternative characterization of the class of context-free languages in terms of recognizing devices. After that paper, these models have been almost forgotten for many years. Only recently, limited automata were reconsidered in a series of works, where several properties of them and of their variants have been investigated. In this talk we will present an overview of the most important results obtained during these researches. We will also discuss some related models and possible lines for future investigations.