main-content

## Über dieses Buch

This book constitutes the refereed proceedings of the 15th International Conference on Developments in Language Theory, DLT 2011, held in Milano, Italy, in July 2011. The 34 regular papers presented were carefully reviewed and selected from numerous submissions. The volume also contains the papers or abstracts of 5 invited speakers, as well as a 2-page abstract for each of the 7 poster papers. The topics covered include grammars, acceptors and transducers for words, trees and graphs; algebraic theories of automata; codes; symbolic dynamics; algorithmic, combinatorial and algebraic properties of words and languages; decidability questions; applications of language theory, including: natural computing, image manipulation and compression, text algorithms, cryptography, concurrency, complexity theory and logic; cellular automata and multidimensional patterns; language theory aspects of quantum computing and bio-computing.

## Inhaltsverzeichnis

### Hunting Redundancies in Strings

The notion of redundancies in texts, regarded as sequences of symbols, appear under various concepts in the literature of Combinatorics on words and of Algorithms on strings: repetitions, repeats, runs, covers, seeds, and palindromes, for example.

We explore some of the newest aspects of these redundancies.

Golnaz Badkobeh, Supaporn Chairungsee, Maxime Crochemore

### Some Remarks on Automata Minimality

It is well known that the minimization problem of deterministic finite automata (

DFAs

) is related to the indistinguishability notion of states (cf. [HMU00]). Indeed, a well known technique to minimize a DFA, essentially, consists in finding pairs of states that are equivalent (or

indistinguishable

), namely pairs of states (

p

,

q

) such that it is impossible to assert the difference between

p

and

q

only by starting in each of the two states and asking whether or not a given input string leads to a final state. Since, in the testing states equivalence, the notion of initial state is irrelevant, some of the main techniques for the minimization of automata, such as Moore’s algorithm [Moo56] and Hopcroft’s algorithm [Hop71], do not care what is the initial state of the automaton, when applied to accessible automata (i.e. such that all states can be reached from the initial state). Therefore a natural question that arises is, for accessible automata, on what does minimality depend? Obviously, it depends on both the automata transitions and the set of final states. In this paper, our main focus is to investigate to what extent minimality depends on the particular subset of final states.

Antonio Restivo, Roberto Vaglica

### Growth Properties of Power-Free Languages

The aim of this paper is to give a short survey of the area formed by the intersection of two popular lines of investigation in formal language theory. The first line, originated by Thue in 1906, concerns about

repetition-free

words and languages. The second line is the study of

growth functions

for words and languages; it can be traced back to the classical papers by Morse and Hedlund on symbolic dynamics (1938, 1940). Growth functions of repetition-free languages are investigated since 1980’s. Most of the results were obtained for power-free languages, but some ideas can be applied for languages avoiding patterns and Abelian-power-free languages as well.

In this paper, we present key contributions to the area, its state-of-the-art, and conjectures that suggest answers to some natural unsolved problems. Also, we pay attention to the tools and techniques that made possible the progress in the area and suggest some technical results that would be useful to solve open problems.

Arseny M. Shur

### A Functional Program for Regular Expressions Matching

Abstract of Invited Talk

Regular expressions [4] and tools to handle them, especially tools for regular expression matching—an early one is described in the seminal paper [5] by Ken Thompson—, are one of the major achievements of formal language and automata theory. Google counts 303,000 results for “regular expressions matching” (May 4, 2011); there are numerous command line tools for working with regular expressions such as grep; Google released a regular expression C++ library not long ago [3]; almost every programming language provides support for regular expressions; and even the text editor I am using to produce the source code of this LaTeX document has an extensive regular expression library.

Thomas Wilke

### State Complexity Research and Approximation

A number of basic questions concerning the state complexity research are discussed, which include why many basic problems weren’t studied earlier, whether there is a general algorithm for state complexity, and whether there is a new approach in this area of research. The new concept of state complexity approximation is also discussed. We show that this new concept can be used to obtain good results when the exact state complexities are difficult to find.

Sheng Yu, Yuan Gao

### Counting the Orderings for Multisets in Consecutive Ones Property and PQ-Trees

A binary matrix satisfies the

consecutive ones property

(C1P) if its columns can be permuted such that the 1s in each row of the resulting matrix are consecutive. Equivalently, a family of

sets

F

= {

Q

1

,...,

Q

m

}, where

Q

i

⊆

R

for some universe

R

, satisfies the C1P if the symbols in

R

can be permuted such that the elements of each set

Q

i

∈

F

occur consecutively, as a contiguous segment of the permutation of

R

’s symbols. Motivated by combinatorial problems on sequences with repeated symbols, we consider the C1P version on

multisets

and prove that counting the orderings (permutations) thus generated is #P-complete. We prove completeness results also for counting the permutations generated by PQ-trees (which are related to the C1P), thus showing that a polynomial-time algorithm is unlikely to exist when dealing with multisets and sequences with repeated symbols.

Giovanni Battaglia, Roberto Grossi, Noemi Scutellà

### Avoiding Abelian Powers in Partial Words

We study abelian repetitions in partial words, or sequences that may contain some unknown positions or holes. First, we look at the avoidance of abelian

p

th powers in infinite partial words, where

p

> 2, extending recent results regarding the case where

p

= 2. We investigate, for a given

p

, the smallest alphabet size needed to construct an infinite partial word with finitely or infinitely many holes that avoids abelian

p

th powers. We construct in particular an infinite binary partial word with infinitely many holes that avoids 6th powers. Then we show, in a number of cases, that the number of abelian

p

-free partial words of length

n

with

h

holes over a given alphabet grows exponentially as

n

increases. Finally, we prove that we cannot avoid abelian

p

th powers under arbitrary insertion of holes in an infinite word.

### Regular Splicing Languages Must Have a Constant

In spite of wide investigations of finite splicing systems in formal language theory, basic questions, such as their characterization, remain unsolved. In search for understanding the class of finite splicing systems, it has been conjectured that a necessary condition for a regular language

L

to be a splicing language is that

L

must have a constant in the Schützenberger’s sense. We prove this longstanding conjecture to be true. The result is based on properties of strongly connected components of the minimal deterministic finite state automaton for a regular splicing language.

Paola Bonizzoni, Natasha Jonoska

### The Average Transition Complexity of Glushkov and Partial Derivative Automata

In this paper, the relation between the Glushkov automaton (

$\mathcal{A}_{\mathrm{pos}}$

) and the partial derivative automaton (

$\mathcal{A}_{\mathrm{pd}}$

) of a given regular expression, in terms of transition complexity, is studied. The average transition complexity of

$\mathcal{A}_{\mathrm{pos}}$

was proved by Nicaud to be linear in the size of the corresponding expression. This result was obtained using an upper bound of the number of transitions of

$\mathcal{A}_{\mathrm{pos}}$

. Here we present a new quadratic construction of

$\mathcal{A}_{\mathrm{pos}}$

that leads to a more elegant and straightforward implementation, and that allows the exact counting of the number of transitions. Based on that, a better estimation of the average size is presented. Asymptotically, and as the alphabet size grows, the number of transitions per state is on average 2.

Broda

et al.

computed an upper bound for the ratio of the number of states of

$\mathcal{A}_{\mathrm{pd}}$

to the number of states of

$\mathcal{A}_{\mathrm{pos}}$

$\frac{1}{2}$

for large alphabet sizes. Here we show how to obtain an upper bound for the number of transitions in

$\mathcal{A}_{\mathrm{pd}}$

, which we then use to get an average case approximation. Some experimental results are presented that illustrate the quality of our estimate.

Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis

### Theory of Átomata

We show that every regular language defines a unique nondeterministic finite automaton (NFA), which we call “átomaton”, whose states are the “atoms” of the language, that is, non-empty intersections of complemented or uncomplemented left quotients of the language. We describe methods of constructing the átomaton, and prove that it is isomorphic to the normal automaton of Sengoku, and to an automaton of Matz and Potthoff. We study “atomic” NFA’s in which the right language of every state is a union of atoms. We generalize Brzozowski’s double-reversal method for minimizing a deterministic finite automaton (DFA), showing that the result of applying the subset construction to an NFA is a minimal DFA if and only if the reverse of the NFA is atomic.

Janusz Brzozowski, Hellis Tamm

### Syntactic Complexity of Ideal and Closed Languages

The state complexity of a regular language is the number of states in the minimal deterministic automaton accepting the language. The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of regular languages is the worst-case syntactic complexity taken as a function of the state complexity

n

of languages in that class. We prove that

n

n

− 1

is a tight upper bound on the complexity of right ideals and prefix-closed languages, and that there exist left ideals and suffix-closed languages of syntactic complexity

n

n

− 1

+

n

− 1, and two-sided ideals and factor-closed languages of syntactic complexity

n

n

− 2

+ (

n

− 2)2

n

− 2

+ 1.

Janusz Brzozowski, Yuli Ye

### Generalized One-Unambiguity

Brüggemann-Klein and Wood have introduced a new family of regular languages, the

one-unambiguous regular languages

, a very important notion in XML DTDs. A regular language

L

is one-unambiguous if and only if there exists a regular expression

E

over the operators of sum, catenation and Kleene star such that

L

(

E

) =

L

and the position automaton of

E

is deterministic. It implies that for a one-unambiguous expression, there exists an equivalent linear-size deterministic recognizer. In this paper, we extend the notion of one-unambiguity to weak one-unambiguity over regular expressions using the complement operator ¬. We show that a DFA with at most (

n

+ 2) states can be computed from a weakly one-unambiguous expression and that it is decidable whether or not a given DFA recognizes a weakly one-unambiguous language.

Pascal Caron, Yo-Sub Han, Ludovic Mignot

### Simulations over Two-Dimensional On-Line Tessellation Automata

We study the notion of simulation over a class of automata which recognize 2D languages (languages of arrays of letters). This class of two-dimensional On-line Tessellation Automata (2OTA) accepts the same class of languages as the class of tiling systems, considered as the natural extension of classical regular word languages to the 2D case. We prove that simulation over 2OTA implies language inclusion. Even if the existence of a simulation relation between two 2OTA is shown to be a NP-complete problem in time, this is an important result since the inclusion problem is undecidable in general in this class of languages. Then we prove the existence of a unique maximal autosimulation relation in a given 2OTA and the existence of a unique minimal 2OTA which is simulation equivalent to this given 2OTA, both computable in polynomial time.

Gérard Cécé, Alain Giorgetti

### Δ-Clearing Restarting Automata and $\makebox{\sf CFL}$

Δ-clearing restarting automata represent a new restricted model of restarting automata which, based on a limited context, can either delete a substring of the current content of its tape or replace a substring by a special auxiliary symbol Δ, which cannot be overwritten anymore, but it can be deleted later. The main result of this paper consists in proving that besides their limited operations, Δ-clearing restarting automata recognize all context-free languages.

Peter Černo, František Mráz

### Enumeration and Decidable Properties of Automatic Sequences

We show that various aspects of

k

-automatic sequences — such as having an unbordered factor of length

n

— are both decidable and effectively enumerable. As a consequence it follows that many related sequences are either

k

-automatic or

k

-regular. These include many sequences previously studied in the literature, such as the recurrence function, the appearance function, and the repetitivity index. We also give a new characterization of the class of

k

-regular sequences. Many results extend to other sequences defined in terms of Pisot numeration systems.

### Languages vs. ω-Languages in Regular Infinite Games

Infinite games are studied in a format where two players, called Player 1 and Player 2, generate a play by building up an

ω

-word as they choose letters in turn. A game is specified by the

ω

-language which contains the plays won by Player 2. We analyze

ω

-languages generated from certain classes

${\cal K}$

of regular languages of finite words (called *-languages), using natural transformations of *-languages into

ω

-languages. Winning strategies for infinite games can be represented again in terms of *-languages. Continuing work of Selivanov (2007) and Rabinovich et al. (2007), we analyze how these “strategy *-languages” are related to the original language class

${\cal K}$

. In contrast to that work, we exhibit classes

${\cal K}$

where strategy representations strictly exceed

${\cal K}$

.

Namit Chaturvedi, Jörg Olschewski, Wolfgang Thomas

### Solving Word Problems in Group Extensions over Infinite Words

Non-Archimedean words have been introduced as a new type of infinite words which can be investigated through classical methods in combinatorics on words due to a length function. The length function, however, takes values in the additive group of polynomials ℤ[t] (and not, as traditionally, in ℕ), which yields various new properties. Non-Archimedean words allow to solve a number of algorithmic problems in geometric and algorithmic group theory. There is a connection to the first-order theory in free groups (Tarski Problems), too.

In the present paper we provide a general method to use infinite words over a discretely ordered abelian group as a tool to investigate certain group extensions for an arbitrary group

G

. The central object is a group E(

A

,

G

) which is defined in terms of a non-terminating, but confluent rewriting system. The group

G

as well as some natural HNN-extensions of

G

embed into E(

A

,

G

) (and still ”behave like”

G

), which makes it interesting to study its algorithmic properties. The main result characterizes when the Word Problem (

WP

) is decidable in all finitely generated subgroups of E(

A

,

G

). We show that this property holds if and only if the Cyclic Membership Problem ”

$u \in \left< \mathinner{v} \right>$

?” is decidable for all

v

∈

G

. Our methods combine combinatorics on words, string rewriting, and group theory.

Volker Diekert, Alexei G. Myasnikov

### Abelian Primitive Words

We investigate Abelian primitive words, which are words that are not Abelian powers. We show the set of Abelian primitive words is not context-free. We can determine whether a word is Abelian primitive in linear time. Also different from classical primitive words, we find that a word may have more than one Abelian root. We also consider enumeration of Abelian primitive words.

### Scattered Context-Free Linear Orderings

We show that it is decidable in exponential time whether the lexicographic ordering of a context-free language is scattered, or a well-ordering.

Zoltán Ésik

### On Prefix Normal Words

We present a new class of binary words: the prefix normal words. They are defined by the property that for any given length

k

, no factor of length

k

has more

a

’s than the prefix of the same length. These words arise in the context of indexing for jumbled pattern matching (a.k.a. permutation matching or Parikh vector matching), where the aim is to decide whether a string has a factor with a given multiplicity of characters, i.e., with a given Parikh vector. Using prefix normal words, we give the first non-trivial characterization of binary words having the same set of Parikh vectors of factors. We prove that the language of prefix normal words is not context-free and is strictly contained in the language of pre-necklaces, which are prefixes of powers of Lyndon words. We discuss further properties and state open problems.

Gabriele Fici, Zsuzsanna Lipták

### On Non-complete Sets and Restivo’s Conjecture

A finite set

S

of words over the alphabet Σ is called non-complete if

$\textit{Fact}(S^*)\ne\Sigma^*$

. A word

$w\in\Sigma^*\setminus\textit{Fact}(S^*)$

is said to be uncompletable. We present a series of non-complete sets

S

k

whose minimal uncompletable words have length 5

k

2

− 17

k

+ 13, where

k

≥ 4 is the maximal length of words in

S

k

. This is an infinite series of counterexamples to Restivo’s conjecture, which states that any non-complete set possesses an uncompletable word of length at most 2

k

2

.

Vladimir V. Gusev, Elena V. Pribavkina

### Self-organization in Cellular Automata: A Particle-Based Approach

For some classes of cellular automata, we observe empirically a phenomenon of self-organization: starting from a random configuration, regular strips separated by defects appear in the space-time diagram. When there is no creation of defects, all defects have the same direction after some time. In this article, we propose to formalise this phenomenon. Starting from the notion of propagation of defect by a cellular automaton formalized in [Piv07b, Piv07a], we show that, when iterating the automaton on a random configuration, defects in one direction only remain asymptotically.

Benjamin Hellouin de Menibus, Mathieu Sablik

### Chop Operations and Expressions: Descriptional Complexity Considerations

The chop or fusion operation was recently introduced in [

S. A. Babu

,

P. K. Pandya

: Chop Expressions and Discrete Duration Calculus.

Modern Applications of Automata Theory

, World Scientific, 2010], where a characterization of regular languages in terms of chop expressions was shown. Simply speaking, the chop or fusion of two words is a concatenation were the touching letters are coalesced, if both letters are equal; otherwise the operation is undefined. We investigate the descriptional complexity of the chop operation and its iteration for deterministic and nondeterministic finite automata as well as for regular expressions. In most cases tight bounds are shown. Moreover, we also consider the conversion problem between finite automata, regular expressions, and chop expressions. Again, for most conversions we get tight bounds in order of magnitude. It is worth mentioning that regular expressions can be transformed into equivalent chop expressions of polynomial size, but chop expressions can be exponentially more succinct than regular expressions.

Markus Holzer, Sebastian Jakobi

### Nodes Connected by Path Languages

We investigate reachability problems on different types of labeled graphs constrained to formal languages from a family

$\mathcal{L}$

. If every language in

$\mathcal{L}$

is accepted by a one-way nondeterministic storage automaton, then we give an appealing characterization of the computational complexity of the labeled graph reachability problem in terms of two-way nondeterministic storage automata with auxiliary worktape that is logarithmic-space bounded. Moreover, we also consider acyclic graphs in the underlying reachability instance, obtaining a lower bound result for auxiliary storage automata that are simultaneously space and time restricted.

Markus Holzer, Martin Kutrib, Ursula Leiter

### Characterizing the Regular Languages by Nonforgetting Restarting Automata

We study nonforgetting R- and nonforgetting deterministic RR-automata of window size one, that is,

nf-R(1)-

and

det-nf-RR(1)

-automata. Our main result shows that the monotone variants of these two types of restarting automata characterize the regular languages. On the other hand, we prove that already the non-monotone deterministic nonforgetting R(1)-automata accept a class of languages that is incomparable to the class of semi-linear languages with respect to inclusion, but that properly includes the class of languages that are accepted by globally deterministic cooperating distributed systems of stateless deterministic R(1)-automata.

Norbert Hundeshagen, Friedrich Otto

### On Two-Way Transducers

We look at some classes of two-way transducers with auxiliary memory and investigate their containment and equivalence problems. We believe that our results are the strongest known to date concerning two-way transducers.

Oscar H. Ibarra, Hsu-Chun Yen

### There Does Not Exist a Minimal Full Trio with Respect to Bounded Context-Free Languages

We solve an old conjecture of Autebert et al. [1] saying that there does not exist any minimal full trio with respect to bounded context-free languages.

Juha Kortelainen, Tuukka Salmi

### Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups

A framework for the study of periodic behaviour of two-way deterministic finite automata (2DFA) is developed. Computations of 2DFAs are represented by a two-way analogue of transformation semigroups, every element of which describes the behaviour of a 2DFA on a certain string

x

. A subsemigroup generated by this element represents the behaviour on strings in

x

+

. The main contribution of this paper is a description of all such monogenic subsemigroups up to isomorphism. This characterization is then used to show that transforming an

n

-state 2DFA over a one-letter alphabet to an equivalent sweeping 2DFA requires exactly

n

+ 1 states, and transforming it to a one-way automaton requires exactly

$\max_{0 \leqslant \ell \leqslant n} G(n-\ell)+\ell+1$

states, where

G

(

k

) is the maximum order of a permutation of

k

elements.

Michal Kunc, Alexander Okhotin

### Deciding Networks of Evolutionary Processors

In this paper we discuss the usage of Accepting Networks of Evolutionary Processors (ANEPs for short) as deciding devices. In this context we define a new halting condition for this model, which seems more coherent with the rest of the theory than the previous such definition, and show that all the computability results reported so far remain valid in the new framework. Moreover, we give a direct and efficient simulation of an arbitrary ANEP by a complete ANEP, thus, showing that the efficiency of deciding a language by ANEPs is not influenced by the network’s topology. Finally, we obtain a surprising characterization of

P

NP

[log]

as the class of languages that can be decided in polynomial time by ANEPs.

Florin Manea

### From Linear Partitions to Parallelogram Polyominoes

We provide a bijection between parallelogram polyominoes and suitable pairs of linear partitions. This lets us design a CAT (Constant Amortized Time) algorithm for generating all parallelogram polyominoes of size

n

using

$O(\sqrt n)$

space.

Roberto Mantaci, Paolo Massazza

### On Brzozowski’s Conjecture for the Free Burnside Semigroup Satisfying x 2 = x 3

In this paper we examine Brzozowski’s conjecture for the two-generated free Burnside semigroup satisfying

x

2

=

x

3

. The elements of this semigroup are classes of equivalent words, and the conjecture claims that all elements are regular languages. The case of the identity

x

2

=

x

3

is the only one, for which Brzozowski’s conjecture is neither proved nor disproved. We prove the conjecture for all the elements containing an overlap-free or an “almost” overlap-free word. In addition, we show that all but finitely many of these elements are “big” languages in terms of growth rate.

Andrey N. Plyushchenko, Arseny M. Shur

### Never Minimal Automata and the Rainbow Bipartite Subgraph Problem

Never minimal automata, introduced in [4], are strongly connected automata which are not minimal for any choice of their final states. In [4] the authors raise the question whether recognizing such automata is a polynomial time task or not. In this paper, we show that the complement of this problem is equivalent to the problem of checking whether or not in an edge-colored graph there is a bipartite subgraph whose edges are colored using all the colors. We prove that this graph theoretic problem is

NP

-complete, showing that checking the property of never-minimality is unlikely a polynomial time task.

Emanuele Rodaro, Pedro V. Silva

### Boolean Algebras of Regular Languages

We characterize up to isomorphism the Boolean algebras of regular languages and of regular aperiodic languages, and show decidability of classes of regular languages related to these characterizations.

Victor Selivanov, Anton Konovalov

### Fife’s Theorem Revisited

We give another proof of a theorem of Fife — understood broadly as providing a finite automaton that gives a complete description of all infinite binary overlap-free words. Our proof is significantly simpler than those in the literature. As an application we give a complete characterization of the overlap-free words that are 2-automatic.

Jeffrey Shallit

### Infinite Words Rich and Almost Rich in Generalized Palindromes

We focus on Θ-rich and almost Θ-rich words over a finite alphabet

$\mathcal{A}$

, where Θ is an involutive antimorphism over

$\mathcal{A}^*$

. We show that any recurrent almost Θ-rich word

u

is an image of a recurrent Θ′-rich word under a suitable morphism, where Θ′ is again an involutive antimorphism. Moreover, if the word

u

is uniformly recurrent, we show that Θ′ can be set to the reversal mapping. We also treat one special case of almost Θ-rich words. We show that every Θ-standard word with seed is an image of an Arnoux-Rauzy word.

Edita Pelantová, Štěpán Starosta

### Models of Pushdown Automata with Reset

We examine various pushdown automaton variants that are architecturally intermediate between the one-way PDA and the two-way PDA (2PDA), where leftward moves of the input head can only reset it to the left end of the tape, and some component of the machine configuration may be “forgotten”, that is, reset to its initial value, whenever such a move is performed. Most of these model variants are shown to be equivalent in power to either the 2PDA or the one-way PDA. One exception is the Resettable Pushdown Automaton (RPDA), where the stack contents are lost every time the input is reset, and which we prove to be intermediate in power between the PDA and the 2PDA. We give full characterizations of the classes of languages recognized by both the deterministic and the nondeterministic versions of the RPDA.

Nuri Taşdemi̇r, A. C. Cem Say

### Towards Dual Approaches for Learning Context-Free Grammars Based on Syntactic Concept Lattices

Recent studies on grammatical inference have demonstrated the benefits of “distributional learning” for learning context-free and context-sensitive languages. Distributional learning models and exploits the relation between strings and contexts in the language of the learning target. There are two main approaches. One, which we call

primal

, constructs nonterminals whose language is characterized by strings. The other, which we call

dual

, uses contexts to characterize the language of a nonterminal of the conjecture grammar. This paper demonstrates and discusses the duality of those approaches by presenting some powerful learning algorithms along the way.

Ryo Yoshinaka

### On Highly Repetitive and Power Free Words

Answering a question of Richomme, Currie and Rampersad proved that 7/3 is the infimum of the real numbers

α

> 2 such that there exists an infinite binary word that avoids

α

-powers but is highly 2-repetitive, i.e., contains arbitrarily large squares beginning at every position. In this paper, we prove similar statements about

β

-repetitive words, for some other

β

’s, on the binary and the ternary alphabets.

### A Sufficient Condition for Erasing Productions to Be Avoidable

In each grammar model, it is an important question whether erasing productions are necessary to generate all languages. Using the concept of grammars with control languages by Salomaa, which offers a uniform treatment of a variety of grammar models, we present a condition on the class of control languages that guarantees that erasing productions are avoidable in the resulting grammar model. On the one hand, this generalizes the previous result that in Petri net controlled grammars, erasing productions can be eliminated. On the other hand, it allows us to infer that the same is true for vector grammars.

Georg Zetzsche

### Encoding Centered Polyominoes by Means of a Regular Language

In [3] the authors proposed a classification of convex polyominoes based on the number of changes of direction in the paths connecting any two cells of a polyomino. More precisely, a convex polyomino is

k

-convex if every pair of its cells can be connected by a monotone path with at most

k

changes of direction. In 1-convex (also called

L

-convex) polyominoes, any two cells can be connected by a path with at most one change of direction.

Daniela Battaglino, Jean Marc Fedou, Andrea Frosini, Simone Rinaldi

### Computational Aspects of Asynchronous Cellular Automata

Cellular Automata (CA) are a computational model widely used in many scientific fields. A CA consists of identical finite automata arranged over a regular lattice (

i

.

e

. every configuration of a CA is an element of

A

where

A

is a finite set of local states). Each automaton updates its state on the basis of its own state and the one of its neighbors according to a local rule. All updates are synchronous.

Jérôme Chandesris, Alberto Dennunzio, Enrico Formenti, Luca Manzoni

### Short 3-Collapsing Words over a 2-Letter Alphabet

Let

$\mathcal{A}=(Q,\Sigma,\delta)$

be a finite deterministic complete automaton.

$\mathcal{A}$

is called

k

-compressible if there is a word

w

∈ Σ

+

such that the image of the state set

Q

under the action of

w

has at most size |

Q

| −

k

, in such case the word

w

is called

k

-compressing for

$\mathcal{A}$

. A word

w

∈ Σ

+

is

k

-collapsing if it is

k

-compressing for each

k

-compressible automaton of the alphabet Σ and it is

k

-synchronizing if it is

k

-compressing for each

k

-compressible automaton with

k

+ 1 states (see [1,2] for details).

Alessandra Cherubini, Achille Frigeri, Brunetto Piochi

### A Cascade Decomposition of Weighted Finite Transition Systems

We consider weighted finite transition systems with weights from naturally ordered semirings. Such semirings comprise distributive lattices as well as the natural numbers with ordinary addition and multiplication, and the max -plus-semiring. For these systems we explore the concepts of covering and cascade product. We show a cascade decomposition result for such weighted finite transition systems using special partitions of the state set of the system. This extends a classical result of automata theory to the weighted setting.

Manfred Droste, Ingmar Meinecke, Branimir Šešelja, Andreja Tepavčević

### Morphic Characterizations in Terms of Insertion Systems with a Context of Length One

Representing a class of languages through operations on its subclasses is a traditional issue within formal language theory. Among the variety of representation theorems for context-free languages, Chomsky-Schützenberger theorem is unique in that it consists of Dyck languages, regular languages, and simple operations. In this work, we obtain some characterizations and representation theorems of context-free languages and regular languages in Chomsky hierarchy by insertion systems, strictly locally testable languages, and morphisms in the framework of Chomsky-Schützenberger theorem.

Kaoru Fujioka

### Inference of Residual Finite-State Tree Automata from Membership Queries and Finite Positive Data

The area of Grammatical Inference centers on

learning algorithms

: Algorithms that infer a description (e.g., a grammar or an automaton) for an unknown formal language from given information in finitely many steps. Various conceivable learning settings have been outlined, and based on those a range of algorithms have been developed. One of the language classes studied most extensively with respect to its algorithmical learnability is the class of regular string languages.

Anna Kasprzik

### On the Representability of Line Graphs

A graph

G

= (

V

,

E

) is representable if there exists a word

W

over the alphabet

V

such that letters

x

and

y

alternate in

W

if and only if (

x

,

y

) ∈

E

for each

x

≠

y

. Such a

W

is called a

word-representant

of

G

. Note that in this paper we use the term graph to mean a finite, simple graph, even though the definition of representable is applicable to more general graphs.

Sergey Kitaev, Pavel Salimov, Christopher Severs, Henning Úlfarsson

### Backmatter

Weitere Informationen