Skip to main content

2010 | Buch

Developments in Language Theory

14th International Conference, DLT 2010, London, ON, Canada, August 17-20, 2010. Proceedings

herausgegeben von: Yuan Gao, Hanlin Lu, Shinnosuke Seki, Sheng Yu

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

insite
SUCHEN

Inhaltsverzeichnis

Frontmatter

Invited Talks

Reaction Systems: A Model of Computation Inspired by Biochemistry

Natural Computing (see, e.g., [5] or [6]) is concerned with human-designed computing inspired by nature as well as with computation taking place in nature. In other words, natural computing investigates models and computational techniques inspired by nature as well as it investigates, in terms of information processing, processes taking place in nature.

Andrzej Ehrenfeucht, Grzegorz Rozenberg
A Brief Excursion Inside the Class of Tiling Recognizable Two-Dimensional Languages

Tiling recognizable two-dimensional languages, also known as REC, generalize recognizable string languages to two dimensions and share with them several theoretical properties. Nevertheless REC is not closed under complementation and this implies that it is intrinsically non-deterministic. As result, all subclasses corresponding to different notion of unambiguity and determinism define a hierarchy inside REC. Moreover we show that some definitions of unambiguity are equivalent to corresponding notions of determinism and therefore correspond decidable classes closed under complementation and linear parsing algorithms.

Dora Giammarresi
The Complexity of Regular(-Like) Expressions

We summarize results on the complexity of regular(-like) expressions and tour a fragment of the literature. In particular we focus on the descriptional complexity of the conversion of regular expressions to equivalent finite automata and

vice versa

, to the computational complexity of problems on regular-like expressions such as, e.g., membership, inequivalence, and non-emptiness of complement, and finally on the operation problem measuring the required size for transforming expressions with additional language operations (built-in or not) into equivalent ordinary regular expressions.

Markus Holzer, Martin Kutrib
On Decision Problems for Simple and Parameterized Machines

We introduce what we believe to be the simplest known classes of language acceptors for which we can prove that decision problems (like universe, disjointness, containment, etc.) are undecidable. We also look at classes with undecidable decision problems and show that the problems become decidable for the “parameterized” versions of the machines.

Oscar H. Ibarra
DNA Computing and Its Implications for Theoretical Computer Science

DNA computing is an area of natural computing based on the idea that molecular biology processes can be used to perform arithmetic and logic operations on information encoded as DNA strands. The aim of this review is to describe some of the ways in which DNA computing research has impacted fields in theoretical computer science. We namely describe how properties of DNA-based information, and in particular the Watson-Crick complementarity of DNA single strands, have influenced areas of theoretical computer science such as formal language theory, coding theory, automata theory and combinatorics on words.

Lila Kari
Numeration Systems: A Link between Number Theory and Formal Language Theory

We survey facts mostly emerging from the seminal results of Alan Cobham obtained in the late sixties and early seventies. We do not attempt to be exhaustive but try instead to give some personal interpretations and some research directions. We discuss the notion of numeration systems, recognizable sets of integers and automatic sequences. We briefly sketch some results about transcendence related to the representation of real numbers. We conclude with some applications to combinatorial game theory and verification of infinite-state systems and present a list of open problems.

Michel Rigo

Regular Papers

Algorithmic Properties of Millstream Systems

Millstream systems have recently been proposed as a formalization of the linguistic idea that natural language should be described as a combination of different modules related by interfaces. In this paper we investigate algorithmic properties of Millstream systems having regular tree grammars as modules and MSO logic as interface logic. We focus on the so-called completion problem: Given trees generated by a subset of the modules, can they be completed into a valid configuration of the Millstream system?

Suna Bensch, Henrik Björklund, Frank Drewes
On a Conjecture by Carpi and D’Alessandro

Recently, Carpi and D’Alessandro [3] have formulated a conjecture whose validity would imply an

O

(

n

2

) upper bound for the minimum length of reset words for synchronizing automata with

n

states. We refute this conjecture as well as a related conjecture by Rystsov [13] and suggest a weaker version that still suffices to achieve a quadratic upper bound.

Mikhail V. Berlinkov
Linking Algebraic Observational Equivalence and Bisimulation

Observability concepts allow to focus on the observable behaviour of a system while abstracting internal details of implementation. In this context, formal verification techniques use behavioural equivalence notions formalizing the idea of indistinguishability of system states. In this paper, we investigate the relation between two behavioural equivalences: the algebraic observational equivalence in the framework of observational algebras with many hidden sorts and automata bisimulation. For that purpose, we propose a transformation of an observational algebra into an infinite deterministic automaton. Consequently, we obtain a subclass of deterministic automata, equivalent to (infinite) Mealy automata, which we call Observational Algebra Automata (OAA). We use a categorical setting to show the equivalence between bisimulation on OAA and algebraic observational equivalence. Therefore we extend the hidden algebras result concerning observational equivalence and bisimulation coincidence to the non-monadic case.

Mouhebeddine Berrima, Narjes Ben Rajeb
Undecidability and Hierarchy Results for Parallel Communicating Finite Automata

Parallel communicating finite automata (PCFAs) are systems of several finite state automata which process a common input string in a parallel way and are able to communicate by sending their states upon request. We consider deterministic and nondeterministic variants and distinguish four working modes. It is known that these systems in the most general mode are as powerful as one-way multi-head finite automata. It is additionally known that the number of heads corresponds to the number of automata in PCFAs in a constructive way. Thus, undecidability results as well as results on the hierarchies induced by the number of heads carry over from multi-head finite automata to PCFAs in the most general mode. Here, we complement these undecidability and hierarchy results also for the remaining working modes. In particular, we show that classical decidability questions are not semi-decidable for any type of PCFAs under consideration. Moreover, it is proven that the number of automata in the system induces infinite hierarchies for deterministic and nondeterministic PCFAs in three working modes.

Henning Bordihn, Martin Kutrib, Andreas Malcher
Inclusion Problems for Patterns with a Bounded Number of Variables

We study the inclusion problems for pattern languages that are generated by patterns with a bounded number of variables. This continues the work by Freydenberger and Reidenbach (Information and Computation 208 (2010)) by showing that restricting the inclusion problem to significantly more restricted classes of patterns preserves undecidability, at least for comparatively large bounds. For smaller bounds, we prove the existence of classes of patterns with complicated inclusion relations, and an open inclusion problem, that are related to the Collatz Conjecture. In addition to this, we give the first proof of the undecidability of the inclusion problem for NE-pattern languages that, in contrast to previous proofs, does not rely on the inclusion problem for E-pattern languages, and proves the undecidability of the inclusion problem for NE-pattern languages over binary and ternary alphabets.

Joachim Bremer, Dominik D. Freydenberger
On the Average Number of States of Partial Derivative Automata

The partial derivative automaton (

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

) is usually smaller than other non-deterministic finite automata constructed from a regular expression, and it can be seen as a quotient of the Glushkov automaton (

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

). By estimating the number of regular expressions that have

ε

as a partial derivative, we compute a lower bound of the average number of mergings of states in

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

and describe its asymptotic behaviour. This depends on the alphabet size,

k

, and its limit, as

k

goes to infinity, is

$\frac12$

. The lower bound corresponds exactly to consider the

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

automaton for the marked version of the regular expression, i.e. where all its letters are made different. Experimental results suggest that the average number of states of this automaton, and of the

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

automaton for the unmarked regular expression, are very close to each other.

Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis
On the Hybrid Černý-Road Coloring Problem and Hamiltonian Paths

The Hybrid Černý-Road coloring problem is investigated for graphs with Hamiltonian paths. We prove that if an aperiodic, strongly connected digraph of costant outdegree with

n

vertices has an Hamiltonian path, then it admits a synchronizing coloring with a reset word of length 2(

n

 − 2)(

n

 − 1) + 1. The proof is based upon some new results concerning locally strongly transitive automata.

Arturo Carpi, Flavio D’Alessandro
Computing Blocker Sets for the Regular Post Embedding Problem

Blocker and coblocker sets are regular languages involved in the algorithmic solution of the Regular Post Embedding Problem. We investigate the computability of these languages and related decision problems.

Pierre Chambart, Philippe Schnoebelen
Rankers over Infinite Words
(Extended Abstract)

We consider the fragments FO

2

,

$\Sigma_2\cap FO^2$

,

$\Pi_2 \cap FO^2$

, and Δ

2

of first-order logic FO[ < ] over finite and infinite words. For all four fragments, we give characterizations in terms of rankers. In particular, we generalize the notion of a ranker to infinite words in two possible ways. Both extensions are natural in the sense that over finite words they coincide with classical rankers, and over infinite words they both have the full expressive power of FO

2

. Moreover, the first extension of rankers admits a characterization of

$\Sigma_2 \cap FO^2$

while the other leads to a characterization of

$\Pi_2 \cap FO^2$

. Both versions of rankers yield characterizations of the fragment Δ

2

 = Σ

2

 ∩ Π

2

. As a byproduct, we also obtain characterizations based on unambiguous temporal logic and unambiguous interval temporal logic.

Luc Dartois, Manfred Kufleitner, Alexander Lauser
Kleene and Büchi Theorems for Weighted Automata and Multi-valued Logics over Arbitrary Bounded Lattices

We show that

${\mathcal L}$

-weighted automata,

${\mathcal L}$

-rational series, and

$\mathcal L$

-valued monadic second-order logic have the same expressive power, for any bounded lattice

$\mathcal L$

and for finite and infinite words. This extends classical results of Kleene and Büchi to arbitrary bounded lattices, without any distributivity assumption that is fundamental in the theory of weighted automata over semirings. In fact, we obtain these results for large classes of strong bimonoids which properly contain all bounded lattices.

Manfred Droste, Heiko Vogler
On Müller Context-Free Grammars

We define context-free grammars with Müller acceptance condition that generate languages of countable words. We establish several elementary properties of the class of Müller context-free languages including closure properties and others. We show that every Müller context-free grammar can be transformed into a normal form grammar in polynomial space without increasing the size of the grammar, and then we show that many decision problems can be solved in polynomial time for Müller context-free grammars in normal form. These problems include deciding whether the language generated by a normal form grammar contains only well-ordered, scattered, or dense words. In a further result we establish a limitedness property of Müller context-free grammars: If the language generated by a grammar contains only scattered words, then either there is an integer

n

such that each word of the language has Hausdorff rank at most

n

, or the language contains scattered words of arbitrarily large Hausdorff rank. We also show that it is decidable which of the two cases applies.

Zoltán Ésik, Szabolcs Iván
Minimization of Deterministic Bottom-Up Tree Transducers

We show that for every deterministic bottom-up tree transducer, a unique equivalent transducer can be constructed which is minimal. The construction is based on a sequence of normalizing transformations which, among others, guarantee that non-trivial output is produced as early as possible. For a deterministic bottom-up transducer where every state produces either none or infinitely many outputs, the minimal transducer can be constructed in polynomial time.

Sylvia Friese, Helmut Seidl, Sebastian Maneth
Two-Way Unary Automata versus Logarithmic Space

We show that each

n

-state unary 2

nfa

(a two-way nondeterministic finite automaton) can be simulated by an equivalent 2

ufa

(an unambiguous 2

nfa

) with a polynomial number of states. Moreover, if L = NL (the classical logarithmic space classes), then each unary 2

nfa

can be converted into an equivalent 2

dfa

(a deterministic two-way automaton), still keeping polynomial the number of states. This shows a connection between the standard logarithmic space complexity and the state complexity of two-way unary automata: it indicates that L could be separated from NL by proving a superpolynomial gap, in the number of states, for the conversion from unary 2NFAs to 2DFAs.

Viliam Geffert, Giovanni Pighizzini
On the Periodicity of Morphic Words

Given a morphism

h

prolongable on

a

and an integer

p

, we present an algorithm that calculates which letters occur infinitely often in congruent positions modulo

p

in the infinite word

h

ω

(

a

). As a corollary, we show that it is decidable whether a morphic word is ultimately

p

-periodic. Moreover, using our algorithm we can find the smallest similarity relation such that the morphic word is ultimately relationally

p

-periodic. The problem of deciding whether an automatic sequence is ultimately weakly

R

-periodic is also shown to be decidable.

Vesa Halava, Tero Harju, Tomi Kärki, Michel Rigo
Compressed Conjugacy and the Word Problem for Outer Automorphism Groups of Graph Groups

It is shown that for graph groups (right-angled Artin groups) the conjugacy problem as well as a restricted version of the simultaneous conjugacy problem can be solved in polynomial time even if input words are represented in a compressed form. As a consequence it follows that the word problem for the outer automorphism group of a graph group can be solved in polynomial time.

Niko Haubold, Markus Lohrey, Christian Mathissen
Using Light to Implement Parallel Boolean Algebra

We design and implement highly parallel algorithms that use light as the tool of computation. An ordinary xerox machine and a box of transparencies constitutes our computer. We find the maximum in a list of

n

-bit numbers of arbitrary length using at most

n

xerox copying steps. We decide, for any graph having

n

vertices and

m

edges, whether a 3-coloring exists in at most 2

n

 + 4

m

copying steps. For large instances of problems such as the 3-color problem, this solution method may require the production of transparencies that display challengingly high densities of information. Our ultimate purpose here is to give hand tested ‘ultra-parallel’ algorithmic procedures that may provide useful suggestions for future optical technologies.

Tom Head
Periodicity in Tilings

Tilings and tiling systems are an abstract concept that arise both as a computational model and as a dynamical system. In this paper, we prove an analog of the theorems of Fagin [9] and Selman and Jones [14] by characterizing sets of periods of tiling systems by complexity classes.

Emmanuel Jeandel, Pascal Vanier
Complexity in Union-Free Regular Languages

We continue the investigation of union-free regular languages that are described by regular expressions without the union operation. We also define deterministic union-free languages as languages recognized by one-cycle-free-path deterministic finite automata, and show that they are properly included in the class of union-free languages. We prove that (deterministic) union-freeness of languages does not accelerate regular operations, except for the reversal in the nondeterministic case.

Galina Jirásková, Tomáš Masopust
Schema for Parallel Insertion and Deletion

We propose a general framework for parallel insertion/deletion operations based on

p

-schemata. A

p

-schema is a set of tuples of words. When being used for parallel insertion of a language into a word, an element of a

p

-schema specifies how to split the given word into factors between which the insertion of the language will take place. Parallel deletion based on a

p

-schema is defined as an ”inverse” operation of parallel insertion based on the

p

-schema. Several well-known language operations are particular cases of

p

-schema-based insertions or deletions: catenation, Kleene star, reverse catenation, sequential insertion, parallel insertion, insertion next to a given letter, contextual insertion, right and left quotient, sequential deletion, parallel deletion. Additional operations that can be defined using

p

-schemata include contextual parallel insertion, as well as parallel insertion (deletion) of exactly

n

words, at most

n

words, an arbitrary number of words. We also consider the decidability and undecidability of existence of solutions of language equations involving

p

-schema-based parallel insertion/deletion.

Lila Kari, Shinnosuke Seki
On Schützenberger Products of Semirings

The Schützenberger product of (ordered) monoids is an essential tool when studying the polynomial operators on Boolean and positive varieties of languages and concatenation hierarchies. Here we consider rather disjunctive varieties of languages and therefore the recognition of languages is by finite idempotent semirings. We define a product of finite idempotent semirings and we show similar results to those concerning Schützenberger products of monoids and ordered monoids.

Ondřej Klíma, Libor Polák
On Language Equations XXK = XXL and XM = N over a Unary Alphabet

It is shown that the recently discovered computational universality in systems of language equations over a unary alphabet occurs already in systems of the simplest form, with one unknown

X

and two equations

XXK

 = 

XXL

and

XM

 = 

N

, where

K

,

L

,

M

,

N

 ⊆ 

a

*

are four regular constants. Every recursive (r.e., co-r.e.) set can be encoded in a unique (least, greatest) solution of a system of such a form. The proofs are carried out in terms of equations over sets of numbers.

Tommi Lehtinen, Alexander Okhotin
Around Dot Depth Two

It is known that the languages definable by formulae of the logics

$FO^{2}[<,S], \Delta_{2}[<,S], LTL[F,P,X,Y]$

are exactly the variety

DA

*

D

. Automata for this class are not known, nor is its precise placement within the dot-depth hierarchy of starfree languages. It is easy to argue that Δ

2

[ < ,

S

] is included in Δ

3

[ < ]; in this paper we show that it is incomparable with

B

2

)[ < ], the boolean combination of Σ

2

[ < ] formulae. Using ideas from Straubing’s “delay theorem”, we extend our earlier work [LPS08] to propose partially-ordered two-way deterministic finite automata with look-around (po2dla) and a new interval temporal logic called LITL and show that they also characterize the variety

DA

*

D

. We give effective reductions from LITL to equivalent

po

2

dla

and from

po

2

dla

to equivalent

FO

2

[ < ,

S

]. The

po

2

dla

automata admit efficient operations of boolean closure and the language non-emptiness of

po

2

dla

is NP-complete. Using this, we show that satisfiability of LITL remains NP-complete assuming a fixed look-around length. (Recall that for LTL[F,X], it is P

space

-hard.)

Kamal Lodaya, Paritosh K. Pandya, Simoni S. Shah
Input Products for Weighted Extended Top-Down Tree Transducers

A weighted tree transformation is a function

$\tau \colon T_\Sigma \times T_\Delta \to A$

where

T

Σ

and

T

Δ

are the sets of trees over the ranked alphabets Σ and Δ, respectively, and

A

is the domain of a semiring. The input and output product of

τ

with tree series

$\varphi \colon T_\Sigma \to A$

and

$\psi \colon T_\Delta \to A$

are the weighted tree transformations

$\varphi \triangleleft \tau$

and

$\tau \triangleright \psi$

, respectively, which are defined by

$(\varphi \triangleleft \tau)(t, u) = \varphi(t) \cdot \tau(t, u)$

and

$(\tau \triangleright \psi)(t, u) = \tau(t, u) \cdot \psi(u)$

for every

t

 ∈ 

T

Σ

and

u

 ∈ 

T

Δ

. In this contribution, input and output products of weighted tree transformations computed by weighted extended top-down tree transducers (wxtt) with recognizable tree series are considered. The classical approach is presented and used to solve the simple cases. It is shown that input products can be computed in three successively more difficult scenarios: nondeleting wxtt, wxtt over idempotent semirings, and weighted top-down tree transducers over rings.

Andreas Maletti
Regular Hedge Language Factorization Revisited

We consider the factorization problem of regular hedge languages. This problem is strongly related to the type checking problem in rule based transformations of valid XML documents. We propose the representation of regular hedge languages by reduced, complete, and deterministic linear hedge automata, and indicate algorithms for the computation of right factors and factor matrix.

Mircea Marin, Temur Kutsia
Fast Parsing for Boolean Grammars: A Generalization of Valiant’s Algorithm

The well-known parsing algorithm for the context-free grammars due to Valiant (”General context-free recognition in less than cubic time”,

Journal of Computer and System Sciences

, 10:2 (1975), 308–314) is refactored and generalized to handle the more general Boolean grammars. The algorithm reduces construction of the parsing table to computing multiple products of Boolean matrices of various size. Its time complexity on an input string of length

n

is

$O(\mathit{BMM}(n) \log n)$

, where

$\mathit{BMM}(n)$

is the number of operations needed to multiply two Boolean matrices of size

n

×

n

, which is

O

(

n

2.376

) as per the current knowledge.

Alexander Okhotin
On Lexicalized Well-Behaved Restarting Automata That Are Monotone

We introduce lexicalized well-behaved restarting automata as a model of the gradual lexicalized syntactic disambiguation of natural languages. This model presents a non-correctness preserving counter-part to the (correctness preserving) models of analysis by reduction of natural languages. We study two types of gradual relaxations of the correctness preserving property for monotone automata of this type. They lead to two infinite hierarchies of language classes. The basic levels of these hierarchies coincide with the class

LRR

of left-to-right regular languages, and the hierarchies exhaust the class of context-free languages.

Friedrich Otto, Martin Plátek, František Mráz
On a Powerful Class of Non-universal P Systems with Active Membranes

We prove that uniform and semi-uniform families of P systems with active membranes using only communication and nonelementary division rules are not computationally universal. However, they are powerful enough to solve exactly the problems solvable by Turing machines operating in time and space that are ”tetrational” (i.e., bounded by a stack of exponentials of polynomial height) with respect to the size of the input.

Antonio E. Porreca, Alberto Leporati, Claudio Zandron
State Complexity of Prefix, Suffix, Bifix and Infix Operators on Regular Languages

We consider four operators on a regular language. Each of them is a tool for constructing a code (respectively

prefix

,

suffix

,

bifix

and

infix

) out of a given regular language. We give the precise values of the (deterministic) state complexity of each of these operators.

Elena V. Pribavkina, Emanuele Rodaro
Restricted Ambiguity of Erasing Morphisms

A morphism

h

is called ambiguous for a string

s

if there is another morphism that maps

s

to the same image as

h

; otherwise, it is called unambiguous. In this paper, we examine some fundamental problems on the ambiguity of erasing morphisms. We provide a detailed analysis of so-called ambiguity partitions, and our main result uses this concept to characterise those strings that have a morphism of strongly restricted ambiguity. Furthermore, we demonstrate that there are strings for which the set of unambiguous morphisms, depending on the size of the target alphabet of these morphisms, is empty, finite or infinite. Finally, we show that the problem of the existence of unambiguous erasing morphisms is equivalent to some basic decision problems for nonerasing multi-pattern languages.

Daniel Reidenbach, Johannes C. Schneider
Automata with Extremal Minimality Conditions

It is well known that the minimality of a deterministic finite automaton (DFA) depends on the set of final states. In this paper we study the minimality of a strongly connected DFA by varying the set of final states. We consider, in particular, some extremal cases. A strongly connected DFA is called

uniformly minimal

if it is minimal, for any choice of the set of final states. It is called

never-minimal

if it is not minimal, for any choice of the set of final states. We show that there exists an infinite family of uniformly minimal automata and that there exists an infinite family of never-minimal automata. Some properties of these automata are investigated and, in particular, we consider the complexity of the problem to decide whether an automaton is uniformly minimal or never-minimal.

Antonio Restivo, Roberto Vaglica
On the Existence of Minimal β-Powers

If all proper factors of a word

u

are

β

-power-free while

u

itself is not, then

u

is a minimal

β

-power. We consider the following general problem: for which numbers

k

,

β

, and

p

there exists a

k

-ary minimal

β

-power of period

p

? For the case

β

 ≥ 2 we completely solve this problem. If the number

β

< 2 is relatively ”big” w.r.t.

k

, we show that any number

p

can be the period of a minimal

β

-power. Finally, for ”small”

β

we describe some sets of forbidden periods and provide a numerical evidence that for

k

 ≥ 9 these sets are almost exhaustive.

Arseny M. Shur
The Averaging Trick and the Černý Conjecture

The results of several papers concerning the Černý conjecture are deduced as consequences of a simple idea that I call the averaging trick. This idea is implicitly used in the literature, but no attempt was made to formalize the proof scheme axiomatically. Instead, authors axiomatized classes of automata to which it applies.

Benjamin Steinberg

Short Papers

Pseudo-power Avoidance

Since Thue’s work [10] in the early 1900’s, repetition avoidance has been intensely studied [9,8,7,4]. From the point of view of DNA computing [5], we study another type of repetition, called a pseudo-power, inspired by the property of the Watson- Crick complementarity in molecular biology.

Ehsan Chiniforooshan, Lila Kari, Zhi Xu
On Restricted Context-Free Grammars

In context-free grammars, each derivation step can be characterized so that (i) a nonterminal of the current sentential form is chosen and (ii) rewritten by a rule. However, it is well-known that context-free grammars are not able to cover all aspects of natural languages and/or programming languages. Therefore, there were defined many grammars with context-free rules and some mechanism controlling the application of rules, e. g., in random context grammars and their variants, a rule is only applicable if the current sentential form contains some letters or subwords and some letters or words do not occur in it. Therefore, in grammars controlled by context, each derivation step can be characterized so that (i) subsets of applicable nonterminals and rules are determined according to the symbols appearing in the current sentential form, (ii) an applicable nonterminal is chosen and (iii) rewritten by an applicable rule.

Jürgen Dassow, Tomáš Masopust
Graphs Capturing Alternations in Words

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

. If

W

is

k

-uniform (each letter of

W

occurs exactly

k

times in it) then

G

is called

k

-representable. A graph is representable if and only if it is

k

-representable for some

k

[1].

Magnús M. Halldórsson, Sergey Kitaev, Artem Pyatkin
On the Iterated Hairpin Completion

The hairpin completion is a natural operation on formal languages which has been inspired by biochemistry and DNA-computing. In this paper we solve two problems which were posed first in 2008 and 2009, respectively, and still left open:

1

It is known that the iterated hairpin completion of a regular language is not context-free in general, but it was open whether the iterated hairpin completion of a singleton or finite language is regular or at least context-free. We will show that it can be non-context-free.

1

A restricted but also very natural variant of the hairpin completion is the bounded hairpin completion. It was unknown whether the iterated bounded hairpin completion of a regular language remains regular. We prove that this is indeed the case.

Steffen Kopecki
On Lookahead Hierarchies for Monotone and Deterministic Restarting Automata with Auxiliary Symbols (Extended Abstract)

A restarting automaton is a special type of linearly bounded automaton with fixed lookahead length

k

, whose computation proceeds in cycles performing one length-reducing rewrite of the lookahead contents per cycle as the only modification of the input. Through various restrictions on this machine model, a vast number of traditional and new language classes have been excavated. In two studies on lookahead hierarchies for restarting automata without auxiliary symbols [2,3], it was shown that lookahead length is often a significant restriction on the power of these types of restarting automata. No similar study on lookahead hierarchies for restarting automata with auxiliary symbols has been explicitly carried out.

Natalie Schluter
Joint Topologies for Finite and Infinite Words

Infinite words are often considered as limits of finite words. As topological methods have been proved to be useful in the theory of

ω

-languages it seems to be providing to include finite and infinite words into one (topological) space. The attempts so far (see [3, Section 2.4]) have their drawbacks.

Therefore, in the present paper we investigate the possibility to join separate topologies on the space of finite words with a topology in the space of infinite words via a natural mapping. A requirement in this linking of topologies consists in the compatibility of topological properties (opennenss, closedness etc) of images with pre-images and vice versa.

Here we choose the natural

Cantor

topology for infinite words and the

δ

-limit as linking mapping, nad we show that several natural topologies on the space of finite words prove to be compatible with the topology of the

Cantor

space. It is interesting to observe that besides the well-known prefix topology there are at least two more whose origin is from language theory, from the construction of centers and super-centers of languages.

These center- and supercenter-topologies on the space of finite words,

$\mathcal{T}_{c}$

and

$\mathcal{T}_{sc}$

, respectively, fit into the class of

$\mathcal{L}$

-topologies investigated in [2]. Moreover they exhibit special properties within the classes of topologies compatible with the

Cantor

topology.

The paper presents the main results, omitting, however, due to lack of space the results on

$\mathcal{L}$

-topologies. For notation see Sections 1 and 2.1 of [3], and for topological background see e.g. [1].

Ludwig Staiger
Backmatter
Metadaten
Titel
Developments in Language Theory
herausgegeben von
Yuan Gao
Hanlin Lu
Shinnosuke Seki
Sheng Yu
Copyright-Jahr
2010
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-14455-4
Print ISBN
978-3-642-14454-7
DOI
https://doi.org/10.1007/978-3-642-14455-4