Language and Automata Theory and Applications

The present paper surveys recent developments in algorithmic teaching. First, the traditional teaching dimension model is recalled.

Starting from the observation that the teaching dimension model sometimes leads to counterintuitive results, recently developed approaches are presented. Here, main emphasis is put on the following aspects derived from human teaching/learning behavior: the order in which examples are presented should matter; teaching should become harder when the memory size of the learners decreases; teaching should become easier if the learners provide feedback; and it should be possible to teach infinite concepts and/or finite and infinite concept classes.

Recent developments in the algorithmic teaching achieving (some) of these aspects are presented and compared.

This tutorial will present an overview of the use of Monadic Second-Order Logic to describe sets of finite graphs and graph transformations, in relation with the notions of tree-width and clique-width. It will review applications to the construction of algorithms, to Graph Theory and to the extension to graphs of Formal Language Theory concepts.

Over the last half century, a vast literature documenting the importance of deterministic, nondeterministic, and alternating finite automata as an enormously valuable concept has been developed. In the present paper, we tour a fragment of this literature. Mostly, we discuss developments relevant to finite automata related problems like, for example, (i) simulation of and by several types of finite automata, (ii) standard automata problems such as, e.g., fixed and general membership, emptiness, universality, equivalence, and related problems, and (iii) minimization and approximation. We thus come across descriptional and computational complexity issues of finite automata. We do not prove these results but we merely draw attention to the big picture and some of the main ideas involved.

In this paper we survey some results in inductive inference showing how learnability of a class of languages may depend on hypothesis space chosen. We also discuss results which consider how learnability is effected if one requires learning with respect to every suitable hypothesis space. Additionally, optimal hypothesis spaces, using which every learnable class is learnable, is considered.

We discuss techniques to establish lower bounds for the number of states of finite automata operating on nested words. To illustrate these methods we establish a lower bound for the state complexity of Kleene star that is of a different order than the known tight state complexity bound for the star of ordinary regular languages. We survey known bounds on deterministic and nondeterministic state complexity of basic operations on regular nested word languages and discuss open problems.

We use language theory to study the relative expressiveness of infinite-state models laying in between finite automata and Turing machines. We focus here our attention on well structured transition systems that extend Petri nets. For these models, we study the impact of whole-place operations like transfers and resets on nets with indistinguishable tokens and with tokens that carry data over an infinite domain. Our measure of expressiveness is defined in terms of the class of languages recognized by a given model using coverability of a configuration as accepting condition.

A regular language is called

union-free

if it can be represented by a regular expression that does not contain the union operation. Every regular language can be represented as a finite union of union-free languages (the so-called

union-free decomposition

), but such decomposition is not necessarily unique. We call the number of components in the minimal union-free decomposition of a regular language

the union width

of the regular language. In this paper we prove that the union width of any regular language can be effectively computed and we present an algorithm for constructing a corresponding decomposition. We also study some properties of union-free languages and introduce a new algorithm for checking whether a regular language is union-free.

To develop computational learning theory of commutative regular shuffle closed languages, we study finite elasticity for classes of (semi)group-like structures. One is the class of

A

ℕ

d

 + 

F

such that

A

is a matrix of size

e

×

d

with nonnegative integer entries and

F

consists of at most

k

number of

e

-dimensional nonnegative integer vectors, and another is the class

$\mathcal{X}^{d}_{k}$

of

A

ℤ

d

 + 

F

such that

A

is a square matrix of size

d

with integer entries and

F

consists of at most

k

number of

d

-dimensional integer vectors (

F

is repeated according to the lattice

A

ℤ

d

). Each class turns out to be the elementwise unions of

k

-copies of a more manageable class. So we formulate “learning time” of a class and then study in general setting how much “learning time” is increased by the elementwise union, by using Ramsey number. We also point out that such a standpoint can be generalized by using Noetherian spaces.

We consider policies that are described by regular expressions, finite automata, or formulae of linear temporal logic (LTL). Such policies are assumed to describe situations that are problematic, and thus should be avoided. Given a trace pattern

u

, i.e., a sequence of action symbols and variables, were the variables stand for unknown (i.e., not observed) sequences of actions, we ask whether

u

potentially violates a given policy

L

, i.e., whether the variables in

u

can be replaced by sequences of actions such that the resulting trace belongs to

L

. We also consider the dual case where the regular policy

L

is supposed to describe all the admissible situations. Here, we want to know whether

u

always adheres to the given policy

L

, i.e., whether all instances of

u

belong to

L

. We determine the complexity of the violation and the adherence problem, depending on whether trace patterns are linear or not, and on whether the policy is assumed to be fixed or not.

We study

real-valued absolutely convergent rational series

, i.e. functions

$r: {\it\Sigma}^* \rightarrow {\mathbb R}$

, defined over a free monoid

${\it\Sigma}^*$

, that can be computed by a multiplicity automaton

A

and such that

$\sum_{w\in {\it\Sigma}^*}|r(w)|<\infty$

. We prove that any absolutely convergent rational series

r

can be computed by a multiplicity automaton

A

which has the property that

r

|

A

|

is simply convergent, where

r

|

A

|

is the series computed by the automaton |

A

| derived from

A

by taking the absolute values of all its parameters. Then, we prove that the set

${\cal A}^{rat}({\it\Sigma})$

composed of all absolutely convergent rational series is semi-decidable and we show that the sum

$\sum_{w\in \Sigma^*}|r(w)|$

can be estimated to any accuracy rate for any

$r\in {\cal A}^{rat}({\it\Sigma})$

. We also introduce a spectral radius-like parameter

ρ

|

r

|

which satisfies the following property:

r

is absolutely convergent iff

ρ

|

r

|

< 1.

Motivated by the open question whether

$\mbox{TC{$^0$}}=\mbox{NC{$^1$}}$

we consider the case of linear size TC

0

. We use the connections between circuits, logic, and algebra, in particular the characterization of

$\mbox{TC{$^0$}}$

in terms of finitely typed monoids. Applying algebraic methods we show that the word problem for finite non-solvable groups cannot be described by a FO+MOD+MAJ[REG] formula using only two variables. This implies a separation result of FO[REG]-uniform linear TC

0

from linear NC

1

.

We consider the following optimization problem: Given an instance of an optimization problem and some optimum solution for this instance, we want to find a good solution for a slightly modified instance. Additionally, the scenario is addressed where the solution for the original instance is not an arbitrary optimum solution, but is chosen amongst all optimum solutions in a most helpful way. In this context, we examine reoptimization of the travelling salesperson problem, in particular MinTSP and MaxTSP as well as their corresponding metric versions. We study the case where the weight of a single edge is modified. Our main results are the following: existence of a 4/3-approximation for the metric MinTSP-problem, a 5/4-approximation for MaxTSP, and a PTAS for the metric version of MaxTSP.

In the application domain of component-based system design, developing theories which support compositional reasoning is notoriously challenging. We define

timed modal specifications

, an automata-based formalism combining modal and timed aspects. As a stepping stone to compositional approaches of timed systems, we define the notions of refinement and consistency, and establish their decidability.

Motivated by strong Karp-Lipton collapse results in bounded arithmetic, Cook and Krajíček [1] have recently introduced the notion of propositional proof systems with advice. In this paper we investigate the following question:

Given a language L

, do there exist polynomially bounded proof systems with advice for L

?

Depending on the complexity of the underlying language

L

and the amount and type of the advice used by the proof system, we obtain different characterizations for this problem. In particular, we show that the above question is tightly linked with the question whether

L

has small nondeterministic instance complexity.

Partial words are sequences over a finite alphabet that may have some undefined positions, or “holes,” that are denoted by

$\ensuremath{\diamond}$

’s. A nonempty partial word is called

bordered

if one of its proper prefixes is compatible with one of its suffixes (here

$\ensuremath{\diamond}$

is compatible with every letter in the alphabet); it is called

unbordered

otherwise. In this paper, we investigate the problem of computing the maximum number of holes a partial word of a fixed length can have and still fail to be bordered.

We propose an algorithm that given as input a full word

w

of length

n

, and positive integers

p

and

d

, outputs (if any exists) a maximal

p

-periodic partial word contained in

w

with the property that no two holes are within distance

d

. Our algorithm runs in

O

(

nd

) time and is used for the study of freeness of partial words. Furthermore, we construct an infinite word over a five-letter alphabet that is overlap-free even after the insertion of an arbitrary number of holes, answering affirmatively a conjecture from Blanchet-Sadri, Mercaş, and Scott.

This work studies automata-based symbolic data structures for representing infinite sets. Such structures are used in particular by verification tools in order to represent the sets of configurations handled during symbolic exploration of infinite state spaces. Our goal is to develop an efficient projection operator for these representations. There are several needs for such an operator during state-space exploration; we focus here on projecting the set of reachable configurations obtained at the end of exploration. An interesting application is the state-space visualization problem, which consists in providing the user with a graphical picture of a relevant fragment of the reachable state space.

For theoretical reasons, the projection of automata-represented sets is inherently costly. The contribution of this paper is to introduce an improved automata-based data structure that makes it possible to reduce in several cases the effective cost of projection. The idea is twofold. First, our structure allows to apply projection to only a part of an automaton, in cases where a full computation is not necessary. Second, the structure is able to store the results of past projection operations, and to reuse them in order to speed up subsequent computations. We show how our structure can be applied to the state-space visualization problem, and discuss some experimental results.

Integer multiplication as one of the basic arithmetic functions has been in the focus of several complexity theoretical investigations. Ordered binary decision diagrams (OBDDs) are one of the most common dynamic data structures for Boolean functions. Only recently it has been shown that the OBDD complexity of the most significant bit of integer multiplication is exponential, answering an open question posed by Wegener (2000). In this paper a larger lower bound is presented, using a simpler proof. Moreover, the best known lower bound on the OBDD complexity for the so-called graph of integer multiplication is improved.

We propose a new formalism for generating picture languages based on an assembly mechanism of tiles that uses rules having a context and a replacement site. More precisely, a picture language will be generated from a finite set of initial pictures by iteratively applying rewriting rules from a given finite set of rules, called a

tiling rule system

(TRuS system). We prove that the TRuS systems have a greater generative capacity than the tiling systems of Giammarresi and Restivo, even in the case of one-letter alphabet picture languages. This is due mainly to the use of the notion of replacement.

We investigate the decidability of the operation problem for T0L languages and subclasses: Fix an operation on formal languages. Given languages from the family considered (0L languages, T0L languages, or their propagating variants), is the application of this operation to the given languages still a language that belongs to the same language family? Observe, that all the Lindenmayer language families in question are anti-AFLs, that is, they are not closed under homomorphisms, inverse homomorphisms, intersection with regular languages, union, concatenation, and Kleene closure. Besides these classical operations we also consider intersection and substitution, since the language families under consideration are not closed under these operations, too. We show that for all of the above mentioned language operations, except for the Kleene closure, the corresponding operation problems of 0L and T0L languages and their propagating variants are not even semidecidable.

We examine decision problems for various classes of convex languages, previously studied by Ang and Brzozowski under the name “continuous languages”. We can decide whether a language

L

is prefix-, suffix-, factor-, or subword-convex in polynomial time if

L

is represented by a DFA, but the problem is PSPACE-hard if

L

is represented by an NFA. If a regular language is not convex, we prove tight upper bounds on the length of the shortest words demonstrating this fact, in terms of the number of states of an accepting DFA. Similar results are proved for some subclasses of convex languages: the prefix-, suffix-, factor-, and subword-closed languages, and the prefix-, suffix-, factor-, and subword-free languages.

In this paper we prove the following result. Let

s

be an infinite word on a finite alphabet, and

N

 ≥ 0 be an integer. Suppose that all left special factors of

s

longer than

N

are prefixes of

s

, and that

s

has at most one right special factor of each length greater than

N

. Then

s

is a morphic image, under an injective morphism, of a suitable standard Arnoux-Rauzy word.

We introduce a tree transducer model combining aspects of both attributed tree transducers and monadic datalog, thereby allowing to specify in one rule information transport for non-adjacent nodes. We show that our model is strictly more powerful than attributed tree transducers, and we identify a large syntactic subclass which is as powerful as attributed tree transducers. This is shown by an effective construction.

In this paper we extend the work of Campeanu, Salomaa and Yu [1] on extended regular expressions featured in the Unix utility

egrep

and the popular scripting language

Perl.

We settle the open issue of closure under intersection and provide an improved pumping lemma that will show that a larger class of languages is not recognizable by extended regular expressions. We also investigate some questions regarding extended multi-pattern languages introduced by Nagy in [2].

Classical algorithms convert arbitrary automata into regular expressions that have an exponential size in the size of the automaton. There exists a well-known family of automata, obtained by the Glushkov construction (of an automaton from an expression) and named Glushkov automata, for which the conversion is linear. Our aim is to extend the family of Glushkov automata. A first step for such an extension is to define a new family of regular operators and to check that the associated extended expressions have good properties: existence of normal forms, succinctness with respect to equivalent simple expressions, and compatibility with Glushkov functions. This paper addresses this first step and investigates the case of multi-tilde operators.

In this paper we begin the study the dynamical behavior of non-uniform cellular automata and compare it to the behavior of “classical” cellular automata. In particular we focus on surjectivity and equicontinuity.

We present conditions which guarantee that a composition of marker cellular automata has the same neighbourhood as each of the individual components. We show that, under certain technical assumptions, a marker cellular automaton has a unique inverse with a given neighbourhood. We use these results to develop a working key generation algorithm for a public-key cryptosystem based on reversible cellular automata originally conceived by Kari. We conclude with a discussion on security and practical considerations for the cryptosystem and give several ideas for future work.

A Petri net controlled grammar is a context-free grammar with a control by a Petri net whose transitions are labeled with rules of the grammar or the empty string and the associated language consists of all terminal strings which can be derived in the grammar and the sequence of rules in a derivation is in the image of a successful occurrence of transitions of the net. We present some results on the generative capacities of such grammars that Petri nets are restricted to some known structural subclasses of Petri nets.

Many algorithms, e.g. in the field of string matching, are based on handling many counters, which can be performed in parallel, even on a sequential machine, using bit-parallelism. The recently presented technique of nested counters (

Matryoshka counters

) [1] is to handle small counters most of the time, and refer to larger counters periodically, when the small counters may get full, to prevent overflow. In this work, we present several non-trivial applications of Matryoshka counters in string matching algorithms, improving their worst- or average-case time complexities. The set of problems comprises (

δ

,

α

)-matching, matching with

k

insertions, episode matching, and matching under Levenshtein distance.

Earliest query answering is needed for streaming XML processing with optimal memory management. We study the feasibility of earliest query answering for node selection queries. Tractable queries are distinguished by a bounded number of concurrently alive answer candidates at every time point, and a bounded delay for node selection. We show that both properties are decidable in polynomial time for queries defined by deterministic automata for unranked trees. Our results are obtained by reduction to the bounded valuedness problem for recognizable relations between unranked trees.

This work provides a comparison of learning by erasing [1] and iterated epistemic update [2] as analyzed in dynamic epistemic logic (see e.g.[3]). We show that finite identification can be modelled in dynamic epistemic logic and that the elimination process of learning by erasing can be seen as iterated belief-revision modelled in dynamic doxastic logic.

We study the effects of faulty data on NP-hard sets. We consider hard sets for several polynomial time reductions, add corrupt data and then analyze whether the resulting sets are still hard for NP. We explain that our results are related to a weakened deterministic variant of the notion of program self-correction by Blum, Luby, and Rubinfeld. Among other results, we use the Left-Set technique to prove that m-complete sets for NP are nonadaptively weakly deterministically self-correctable while btt-complete sets for NP are weakly deterministically self-correctable. Our results can also be applied to the study of Yesha’s p-closeness. In particular, we strengthen a result by Ogiwara and Fu.

Introducing priorities in rewriting increases the expressive power of rules and helps to limit computations. Priority rewriting is used in rule-based programming as well as in functional programming. Termination of priority rewriting is then important to guarantee that programs give a result. We describe an inductive proof method for termination of priority rewriting, relying on an explicit induction on the termination property and working by generating proof trees, which model the rewriting relation by using abstraction and narrowing.

We investigate the state complexity of combined operations for prefix-free regular languages. Prefix-free minimal deterministic finite-state automata have a unique structural property that plays an important role to obtain the precise state complexity of basic operations. Based on the same property, we establish the precise state complexity of four combined operations: star-of-union, star-of-intersection, star-of-reversal and star-of-catenation.

Extended Context-Free Grammars (ECFGs) and Regular Right-Part Grammars (RRPGs) have many applications, but they are sparsely covered in the vast literature on parsing and grammars. This paper presents first steps towards a taxonomy of parsers for ECFGs and RRPGs, in order to make this subject more accessible.

The parameterized pattern matching problem is a kind of pattern matching problem, where a pattern is considered to occur in a text when there exists a renaming bijection on the alphabet with which the pattern can be transformed into a substring of the text. A

parameterized border array

(

p-border array

) is an analogue of a border array of a standard string, which is also known as the failure function of the Morris-Pratt pattern matching algorithm. In this paper we present a linear time algorithm to verify if a given integer array is a valid p-border array for a binary alphabet. We also show a linear time algorithm to compute all binary parameterized strings sharing a given p-border array. In addition, we give an algorithm which computes all p-border arrays of length at most

n

, where

n

is a a given threshold. This algorithm runs in time linear in the number of output p-border arrays.

We consider a restricted variant of the hairpin completion called bounded hairpin completion. The hairpin completion is a formal operation inspired from biochemistry. Applied to a word encoding a single stranded molecule

x

such that either a suffix or a prefix of

x

is complementary to a subword of

x

, hairpin completion produces a new word

z

, which is a prolongation of

x

to the right or to the left by annealing.

The restriction considered here concerns the length of all prefixes and suffixes that are added to the current word by hairpin completion. They cannot be longer than a given constant. Closure properties of some classes of formal languages under the non-iterated and iterated bounded hairpin completion are investigated. We also define the inverse operation, namely bounded hairpin reduction, and consider the set of all primitive bounded hairpin roots of a regular language.

We introduce the class of Rigid Tree Automata (RTA), an extension of standard bottom-up automata on ranked trees with distinguished states called rigid. Rigid states define a restriction on the computation of RTA on trees: RTA can test for equality in subtrees reaching the same rigid state. RTA are able to perform local and global tests of equality between subtrees, non-linear tree pattern matching, and restricted disequality tests as well. Properties like determinism, pumping lemma, boolean closure, and several decision problems are studied in detail. In particular, the emptiness problem is shown decidable in linear time for RTA whereas membership of a given tree to the language of a given RTA is NP-complete. Our main result is the decidability of whether a given tree belongs to the rewrite closure of a RTA language under a restricted family of term rewriting systems, whereas this closure is not a RTA language. This result, one of the first on rewrite closure of languages of tree automata with constraints, is enabling the extension of model checking procedures based on finite tree automata techniques. Finally, a comparison of RTA with several classes of tree automata with local and global equality tests, and with dag automata is also provided.

Self-verifying automata are a special variant of finite automata with a symmetric kind of nondeterminism. In this paper, we study the transformation of self-verifying automata into deterministic automata from a descriptional complexity point of view. The main result is the exact cost, in terms of the number of states, of such a simulation.

We present and compare two methods of how to make derivation in a Tree Adjoining Grammar a regular process (in the Chomsky hierarchy sense) without loss of expressive power. One regularization method is based on an algebraic operation called Lifting, while the other exploits an additional spatial dimension by transforming the components of a TAG into three-dimensional trees. The regularized grammars generate two kinds of “encoded” trees, from which the intended ones can be reconstructed by a simple decoding function. We can show the equivalence of these two two-step approaches by giving a direct translation between lifted and three-dimensional trees and proving that via this translation it is possible to switch between the encodings without losing the information necessary for the reconstruction of the intended trees.

Position Weight Matrices are broadly used probabilistic motif models. In this paper, we address the problem of identifying and characterizing potential overlaps between occurrences of such a motif. It has useful applications to the statistics of the number of occurrences, and to weighted pattern matching with an extension of the well-known Knuth-Morris-Pratt algorithm.

We show that fixed membership testing for many interesting subclasses of multi-pushdown machines is no harder than for pushdowns with single stack. The models we consider are

MVPA

,

OVPA

and

MPDA

, which have all been defined and studied in the past.

Multi-stack pushdown automata,

MPDA

, have ordered stacks with pop access restricted to the stack-top of the first non-empty stack. The membership for

MPDA

s is known to be in NSPACE(

n

) and in

P

. We show that the

P

-time algorithm can be implemented in the complexity class

LogCFL

; thus membership for

MPDA

s is

LogCFL

-complete.

It follows that membership testing for ordered visibly pushdown automata

OVPA

is also in

LogCFL

.

The membership problem for multi-stack visibly pushdown automata,

MVPA

, is known to be

NP

-complete. However, many applications focus on

MVPA

with

O

(1) phases. We show that for

MVPA

with

O

(1) phases, membership reduces to that in

MPDA

s, and so is in

LogCFL

.

In this paper we investigate the computational complexity of knot theoretic problems and show upper and lower bounds for planarity problem of signed and unsigned knot diagrams represented by Gauss words. Due to the fact the number of crossing in knots is unbounded, the Gauss words of knot diagrams are strings over infinite (unbounded) alphabet. For establishing the lower and upper bounds on recognition of knot properties we study these problems in a context of automata models over infinite alphabet.

This paper addresses the time complexity of several queries (including membership and isomorphism) in classes of unary automatic structures and the state complexity of describing these classes. We focus on unary automatic equivalence relations, linear orders, trees, and graphs with finite degree. We prove that in various senses, the complexity of these classes is low: (1) For the isomorphism problem, we either greatly improve known algorithms (reducing highly exponential bounds to small polynomials) or answer open questions about the existence of a decision procedure; (2) for state complexity, we provide polynomial bounds with respect to natural measures of the sizes of the structures.

In 1995 M. Schellekens introduced the theory of complexity spaces as a part of the development of a mathematical (topological) foundation for the complexity analysis of programs and algorithms [Electronic Notes in Theoret. Comput. Sci. 1 (1995), 211-232]. This theory is based on the structure of quasi-metric spaces which allow to measure relative progress made in lowering the complexity when a program is replaced by another one. In his paper, Schellekens showed the applicability of the theory of complexity spaces to the analysis of Divide & Conquer algorithms. Later on, S. Romaguera and Schellekens introduced the so-called dual (quasi-metric) complexity space in order to obtain a more robust mathematical structure for the complexity analysis of programs and algorithms [Topology Appl. 98 (1999), 311-322]. They studied some properties of the original complexity space, which are interesting from a computational point of view, via the analysis of the dual ones and they also gave an application of the dual approach to the complexity analysis of Divide and Conquer algorithms. Most recently, Romaguera and Schellekens introduced and studied a general complexity framework which unifies the original complexity space and the dual one under the same formalism [Quaestiones Mathematicae 23 (2000), 359-374]. Motivated by the former work we present an extension of the generalized complexity spaces of Romaguera and Schellekens and we show, by means of the so-called domain of words, that the new complexity approach is suitable to provide quantitative computational models in Theoretical Computer Science. In particular our new complexity framework is shown to be an appropriate tool to model the meaning of while-loops in formal analysis of high-level programming languages.

Syntactic analysis of natural languages is the fundamental requirement of many applied tasks. We propose a new module between morphological and syntactic analysis that aims at determining the overall structure of a sentence prior to its complete analysis.

We exploit a concept of segments, easily automatically detectable and linguistically motivated units. The output of the module, so-called ‘segmentation chart’, describes the relationship among segments, especially relations of coordination and apposition or relation of subordination.

In this text we present a framework that enables us to develop and test rules for automatic identification of segmentation charts. We describe two basic experiments – an experiment with segmentation patterns obtained from the Prague Dependency Treebank and an experiment with the segmentation rules applied to plain text. Further, we discuss the evaluation measures suitable for our task.

This paper answers three open questions concerning the generative power of some simple variants of context-free grammars regulated by context conditions. Specifically, it discusses the generative power of so-called context-free semi-conditional grammars (which are random context grammars where permitting and forbidding sets are replaced with permitting and forbidding strings) where permitting and forbidding strings of each production are of length no more than one, and of simple semi-conditional grammars where, in addition, no production has attached both a permitting and a forbidding string. Finally, this paper also presents some normal form results, an overview of known results, and unsolved problems.

It is well known that the symmetry bias much accelerates the vocabulary learning. In particular, the bias helps infants to connect objects with their names easily. However, grammar learning is another important aspect of language acquisition. In this study, we propose that the symmetry bias also would help to acquire grammar rules faster. We employ Iterated Learning Model, and revise it to include the symmetry bias. The result of the experiments shows that infants could abduce the meanings from incomprehensible utterances using the symmetry bias, and acquire the compositional grammar from a reduced amount of learning data.

We present a new series of run-rich strings, and give a new lower bound 0.94457567 of the maximum number of runs in a string. We also introduce the general conjecture about a asymptotic behavior of the numbers of runs in the strings defined by any recurrence formula, and show the lower bound can be improved further to 0.94457571235.

In this paper we investigate the computational power of accepting networks of evolutionary processors (ANEP for short) with filters defined in two ways: by regular sets and random contexts conditions, respectively. We consider ANEPs with all the nodes specialized in only one evolutionary operation (substitution, insertion and deletion) or in two operations out of these three.

We show by reduction from the halting problem for Turing machines that typical rule-based models of fine-grained access control of trees make impossible certain forms of analysis, limiting the ability to audit existing policies and evaluate new ones. Fine-grained access control is the problem of specifying the set of operations that may be performed on a complex structure. For tree-structured databases and documents, particularly XML, a rule-based approach is most common. In this model, access control policies consist of rules that select the allowed or disallowed targets of queries based on their hierarchical relationships to other nodes.

We consider the problem of determining whether a given document (that is, a rooted vertex-labelled tree) could have been produced in accordance with a particular access control policy for updates. We show that, for rule-based policies based on a simple fragment of XPath, this problem is undecidable. This result shows that rule-based access control policies based on XPath languages are, in some sense,

too

powerful, demonstrating the need for a model of access control of tree updates that bridges the gap between expressive and analyzable policies.

Creole is a new born language emerging in most cases where language contact takes place. Simulating behaviors that creole communities are formed in some environments, we could contribute to actual proof of some linguistic theories concerning language acquisition. Thus far, a simulation study of the emergence of creoles has been reported in the mathematical framework. In this paper we introduce a spatial structure to the framework. We show that local creole communities are organized, and creolization may occur when language learners learn often from non-parental language speakers, in contrast to the non-spatial model. The quantitative analysis of the result tells us that emergence of local colonies at the early stage tends to induce the full creolization.

Glushkov’s algorithm builds an

ε

-free nondeterministic automaton from a given regular expression. In the worst case, its number of states is linear and its number of transitions is quadratic in the size of the expression. We show in this paper that in average, the number of transitions is linear.

Deciding whether a finite set of polyominoes tiles the plane is undecidable by reduction from the Domino problem. In this paper, we prove that the problem remains undecidable if the set of instances is restricted to sets of 5 polyominoes. In the case of tiling by translations only, we prove that the problem is undecidable for sets of 11 polyominoes.

In this paper, we obtain some characterizations and representation theorems of languages in Chomsky hierarchy by using insertion systems, strictly locally testable languages, and morphisms. For instance, each recursively enumerable language

L

can be represented in the form

L

 = 

h

(

L

(

γ

) ∩ 

R

), where

γ

is an insertion system of weight (3,3),

R

is a strictly 2-testable language, and

h

is a projection. A similar representation can be obtained for context-free languages, using insertion systems of weight (3,0) and strictly 4-testable languages, as well as for regular languages, using insertion systems of weight (1,0) and strictly 2-testable languages.

This paper contributes to the study of Freely Rewriting Re-starting Automata (

FRR

-automata) and Parallel Communicating Grammar Systems (

PCGS

) as formalizations of the linguistic method of

analysis by reduction

. For

PCGS

we study two complexity measures called

generation complexity

and

distribution complexity

, and we prove that a

PCGS

Π

, for which both these complexity measures are bounded by constants, can be simulated by a freely rewriting restarting automaton of a very restricted form. From this characterization it follows that the language

L

(

Π

) is semi-linear, that its characteristic analysis is of polynomial size, and that this analysis can be computed in polynomial time.

A synchronizing word

w

for a given synchronizing DFA is called

minimal

if no proper prefix or suffix of

w

is synchronizing. We characterize the class of synchronizing automata having finite language of minimal synchronizing words (such automata are called

finitely generated

). Using this characterization we prove that any such automaton possesses a synchronizing word of length at most 3

n

 − 5. We also prove that checking whether a given DFA

$\mathcal{A}$

is finitely generated is co-NP-hard, and provide an algorithm for this problem which is exponential in the number of states

$\mathcal{A}.$

We present a novel approach to the synchronization problem. It is a well-known fact that a problem of finding minimal (or: the shortest) synchronizing word (MSW) for a given synchronizing automaton is NP-complete. In this paper we present the genetic algorithm which tries, for a given automaton, to find possibly short word that synchronizes it. We use a modified version of a classical simple genetic algorithm (SGA).

Arithmetical complexity of an infinite word, defined by Avgustinovich, Fon-Der-Flaass and Frid in 2000, is the number of words of length

n

which occur in its arithmetical subsequences. We present a construction of infinite words whose arithmetical complexity function grows faster than any polynomial, but slower than any exponential. Also we give a rough upper bound for the arithmetical complexity of the Sierpiński word.

Gene trees are leaf-labeled trees inferred from molecular sequences. Due to duplication events arising in genome evolution, gene trees usually have multiple copies of some labels,

i.e.

species. Inferring a species tree from a set of multi-labeled gene trees (MUL trees) is a well-known problem in computational biology. We propose a novel approach to tackle this problem, mainly to transform a collection of MUL trees into a collection of evolutionary trees, each containing single copies of labels. To that aim, we provide several algorithmic building stones and describe how they fit within a general species tree inference process. Most algorithms have a linear-time complexity, except for an FPT algorithm proposed for a problem that we show to be intractable.

This paper proposes an alternative approach to the standard notion of rational (or regular) expression for tree languages. The main difference is that in the new notion we have only one concatenation operation and only one star-operation, instead of many different ones. This is achieved by considering forests instead of trees over a ranked alphabet, or, algebraicly speaking, by considering cartesian categories instead of term-algebras. The main result is that in the free cartesian category the rational languages and the recognizable languages coincide. For the construction of the rational expression for a recognizable language it is not necessary to extend the alphabet. We only use operations that can be defined with the algebraic structure provided by cartesian categories.

ε

-IRTA are a subclass of timed automata with

ε

moves (

ε

-TA). They are useful for modelling global sparse time base used in time-triggered architecture and distributed business processes. In a previous paper [1], the language inclusion problem

$L({\mathcal A}) \subseteq L(\mathcal B$

was shown to be decidable when

$\mathcal A$

is an

ε

-TA and

$\mathcal B$

is an

ε

-IRTA. In this paper, we address the determinization, complementation and

ε

-removal questions for

ε

-IRTA. We introduce a new variant of timed automata called GRTA. We show that for every

ε

-IRTA we can effectively construct a language equivalent 1-clock, deterministic GRTA with

periodic time guards

(but having no

ε

moves). The construction gives rise to at most a double exponential blowup in the number of locations. Finally, we show that every GRTA with periodic guards can be reduced to a language equivalent

ε

-IRTA with at most double the number of locations. Thus,

ε

-IRTA, periodic GRTA, and deterministic 1-clock periodic GRTA have the same expressive power and that they are all expressively complete with respect to the regular

δ

$\checkmark$

-languages. Equivalence of deterministic and nondeterministic automata also gives us that these automata are closed under the boolean operations.

We study the complexity of identifying (learning) timed automata in the limit from data. In previous work, we showed that in order for timed automata to be efficiently identifiable in the limit, it is necessary that they are deterministic and that they use at most one clock. In this paper, we show this is also sufficient: we provide an algorithm that identifies one-clock deterministic timed automata efficiently in the limit.