We investigate the expressive power of first-order quantifications in the
context of monadic second-order logic over pictures. We show that k+1 set
quantifier alternations allow to define a picture language that cannot be
defined using k set quantifier alternations preceded by arbitrarily many
first-order quantifier alternations. The approach uses, for a given picture
language L and an integer m > 0 the height-m fragment of L, which is defined as
the word language obtained by considering each picture p of height m in L as a
word, where the letters of that word are the columns of p.

We show that deterministic finite automata equipped with $k$ two-way heads
are equivalent to deterministic machines with a single two-way input head and
$k-1$ linearly bounded counters if the accepted language is strictly bounded,
i.e., a subset of $a_1^*a_2^*... a_m^*$ for a fixed sequence of symbols $a_1,
a_2,..., a_m$. Then we investigate linear speed-up for counter machines. Lower
and upper time bounds for concrete recognition problems are shown, implying
that in general linear speed-up does not hold for counter machines.

Linguistic variables represent crisp information in a form and precision
appropriate for the problem. For example, to answer the question "How are you?"
one may say "I am fine." the linguistic variables like "fine", so common in
everyday speech. In this paper an alternative interpretation of linguistic
variables is introduced with the notion of a linguistic description of a value
or set of values. The use of linguistic variables in many applications reduces
the overall computation complexity of the application.

In this paper, we study several decision problems for functional weighted
automata. To associate values with runs, we consider four different measure
functions: the sum, the mean, the discounted sum of weights along edges and the
ratio between rewards and costs. On the positive side, we show that the
existential and universal threshold problems, the language inclusion problem
and the equivalence problem are all decidable for the class of functional
weighted automata and the four measure functions that we consider.

We compare tools for complementing nondeterministic B\"uchi automata with a
recent termination-analysis algorithm. Complementation of B\"uchi automata is a
key step in program verification. Early constructions using a Ramsey-based
argument have been supplanted by rank-based constructions with exponentially
better bounds. In 2001 Lee et al. presented the size-change termination (SCT)
problem, along with both a reduction to B\"uchi automata and a Ramsey-based
algorithm.

Regular expressions provide a flexible means for matching strings and they
are often used in data-intensive applications. They are formally equivalent to
either deterministic finite automata (DFAs) or nondeterministic finite automata
(NFAs). Both DFAs and NFAs are affected by two problems known as amnesia and
acalculia, and DFAs are also affected by a problem known as insomnia. Existing
techniques require an automata conversion and compaction step that prevents the
use of existing automaton databases and hinders the maintenance of the
resulting compact automata.

In this paper we study an abelian version of the notion of return word. Our
main result is a new characterization of Sturmian words via abelian returns.
Namely, we prove that a word is Sturmian if and only if each of its factors has
two or three abelian returns. In addition, we describe the structure of abelian
returns in Sturmian words, and discuss connections between abelian returns and
periodicity.

We study the structure of the language of binary cube-free words. Namely, we
are interested in the cube-free words that cannot be infinitely extended
preserving cube-freeness. We show the existence of such words with arbitrarily
long finite extensions, both to one side and to both sides.

A classical result (often credited to Y. Medvedev) states that every language
recognized by a finite automaton is the homomorphic image of a local language,
over a much larger so-called local alphabet, namely the alphabet of the edges
of the transition graph. Local languages are characterized by the value k=2 of
the sliding window width in the McNaughton and Papert's infinite hierarchy of
strictly locally testable languages (k-slt).

Trapezoidal words are finite words having at most n+1 distinct factors of
length n, for every n>=0. They encompass finite Sturmian words. We distinguish
trapezoidal words into two disjoint subsets: open and closed trapezoidal words.
A trapezoidal word is closed if its longest repeated prefix has exactly two
occurrences in the word, the second one being a suffix of the word. Otherwise
it is open. We show that open trapezoidal words are all primitive and that
closed trapezoidal words are all Sturmian. We then show that trapezoidal
palindromes are closed (and therefore Sturmian).

We give a new proof for the decidability of the D0L ultimate periodicity
problem based on the decidability of p-periodicity of morphic words adapted to
the approach of Harju and Linna.

In recent years codes that are not Uniquely Decipherable (UD) are been
studied partitioning them in classes that localize the ambiguities of the code.
A natural question is how we can extend the notion of maximality to codes that
are not UD. In this paper we give an answer to this question. To do this we
introduce a partial order in the set of submonoids of a monoid showing the
existence, in this poset, of maximal elements that we call full monoids. Then a
set of generators of a full monoid is, by definition, a maximal code.

We define the notion of circular words, then consider on such words a
constraint derived from the Fibonacci condition. We give several results on the
structure of these circular words, then mention possible applications to
various situations: periodic expansion of numbers in numeration systems,
"gcd-property" of integer sequences, partition of the prefix of the fixed point
of the Fibonacci substitution, spanning trees of a wheel. Eventually, we
mention some open questions.

We consider the following problem. Let us fix a finite alphabet A; for any
given d-uple of letter frequencies, how to construct an infinite word u over
the alphabet A satisfying the following conditions: u has linear complexity
function, u is uniformly balanced, the letter frequencies in u are given by the
given d-uple. This paper investigates a construction method for such words
based on the use of mixed multidimensional continued fraction algorithms.

Classically in combinatorics on words one studies unavoidable regularities
that appear in sufficiently long strings of symbols over a fixed size alphabet.
In this paper we take another viewpoint and focus on combinatorial properties
of long words in which the number of occurrences of any symbol is restritced by
a fixed constant. We then demonstrate the connection of these properties to
constructing multicollision attacks on so called generalized iterated hash
functions.

In this paper we study $\nu$-CA on one-dimensional lattice defined over a
finite set of local rules. The main goal is to determine how the local rules
can be mixed to ensure the produced $\nu$-CA has some properties. In a first
part, we give some background for the study of $\nu$-CA. Then surjectivity and
injectivity are studied using a variant of DeBruijn graphs. The next part is
dedicated to the number-conserving property.

The value 1 problem is a decision problem for probabilistic automata over
finite words: given a probabilistic automaton, are there words accepted with
probability arbitrarily close to 1? This problem was proved undecidable
recently. We introduce a new class of probabilistic automata, called leaktight
automata, for which the value 1 problem is decidable. The algorithm is based on
the computation of a monoid abstracting the behaviors of the automaton. The
correctness proof relies on algebraic techniques developped by Simon.

Minimal deterministic finite automata (DFAs) can be reduced further at the
expense of a finite number of errors. Recently, such minimization algorithms
have been improved to run in time O(n log n), where n is the number of states
of the input DFA, by [Gawrychowski and Je\.z: Hyper-minimisation made
efficient. Proc. MFCS, LNCS 5734, 2009] and [Holzer and Maletti: An n log n
algorithm for hyper-minimizing a (minimized) deterministic automaton. Theor.
Comput. Sci. 411, 2010]. Both algorithms return a DFA that is as small as
possible, while only committing a finite number of errors.

Recently, two types of simulations (forward and backward simulations) and
four types of bisimulations (forward, backward, forward-backward, and
backward-forward bisimulations) between fuzzy automata have been introduced. If
there is at least one simulation/bisimulation of some of these types between
the given fuzzy automata, it has been proved that there is the greatest
simulation/bisimulation of this kind.

We show that a subclass of infinite-state probabilistic programs that can be
modeled by probabilistic one-counter automata (pOC) admits an efficient
quantitative analysis. In particular, we show that the expected termination
time can be approximated up to an arbitrarily small relative error with
polynomially many arithmetic operations, and the same holds for the probability
of all runs that satisfy a given omega-regular property.

A set $X\subseteq\mathbb N$ is S-recognizable for an abstract numeration
system S if the set $\rep_S(X)$ of its representations is accepted by a finite
automaton. We show that the growth function of an S-recognizable set is always
either $\Theta((\log(n))^{c-df}n^f)$ where $c,d\in\mathbb N$ and $f\ge 1$, or
$\Theta(n^r \theta^{\Theta(n^q)})$, where $r,q\in\mathbb Q$ with $q\le 1$. If
the number of words of length n in the numeration language is bounded by a
polynomial, then the growth function of an S-recognizable set is $\Theta(n^r)$,
where $r\in \mathbb Q$ with $r\ge 1$.

It is important to enable reasoning about the meaning and possible effects of
updates to ensure that the updated system operates correctly. A formal,
mathematical model of dynamic update should be developed, in order to
understand by both users and implementors of update technology what design
choices can be considered. In this paper, we define a formal calculus
$update\pi$, a variant extension of higher-order $\pi$ calculus, to model
dynamic updates of component-based software, which is language and technology
independent.

Timed automata and register automata are well-known models of computation
over timed and data words respectively. The former has clocks that allow to
test the lapse of time between two events, whilst the latter includes registers
that can store data values for later comparison. Although these two models
behave in appearance differently, several decision problems have the same
(un)decidability and complexity results for both models. As a prominent
example, emptiness is decidable for alternating automata with one clock or
register, both with non-primitive recursive complexity.

Combined traces (i.e., comtraces), a generalization of Mazurkiewicz traces,
were introduced by Janicki and Koutny in 1995 as congruence classes of step
sequences, where the congruence relation is induced by two relations
simultaneity and serializability on events. They also showed that comtraces
corresponds to some class of labeled stratified order structures, but the
question "what class of labeled stratified orders represent comtraces?" was
left open. In this work, we proposed a class of labeled stratified order
structures that captures exactly the comtrace notion.

We show how to efficiently enumerate a class of finite-memory stochastic
processes using the causal representation of epsilon-machines. We characterize
epsilon-machines in the language of automata theory and adapt a recent
algorithm for generating accessible deterministic finite automata, pruning this
over-large class down to that of epsilon-machines. As an application, we
exactly enumerate topological epsilon-machines up to seven states and
six-letter alphabets.

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 study the syntactic complexity of the class of
regular ideal languages and their complements, the closed languages.

We present upper and two-sided bounds of the exponential growth rate for a
wide range of power-free languages. All bounds are obtained with the use of
algorithms previously developed by the author.

A language L is closed if L = L*. We consider an operation on closed
languages, L-*, that is an inverse to Kleene closure. We prove that if L is
closed and regular, then L-* is regular. However, the analogous result fails to
hold for the context-free languages. Along the way we find a new relationship
between the unbordered words and the prime palstars of Knuth, Morris, and
Pratt. We use this relationship to enumerate the prime palstars, and we prove
that neither the language of all unbordered words nor the language of all prime
palstars is context-free.

Finite-state complexity is a variant of algorithmic information theory
obtained by replacing Turing machines with finite transducers. We consider the
state-size of transducers needed for minimal descriptions of arbitrary strings
and, as our main result, we show that the state-size hierarchy with respect to
a standard encoding is infinite. We consider also hierarchies yielded by more
general computable encodings.

We define a two-step learner for RFSAs based on an observation table by using
an algorithm for minimal DFAs to build a table for the reversal of the language
in question and showing that we can derive the minimal RFSA from it after some
simple modifications. We compare the algorithm to two other table-based ones of
which one (by Bollig et al. 2009) infers a RFSA directly, and the other is
another two-step learner proposed by the author. We focus on the criterion of
query complexity.

We investigate the nondeterministic state complexity of basic operations for
suffix-free regular languages. The nondeterministic state complexity of an
operation is the number of states that are necessary and sufficient in the
worst-case for a minimal nondeterministic finite-state automaton that accepts
the language obtained from the operation. We consider basic operations
(catenation, union, intersection, Kleene star, reversal and complementation)
and establish matching upper and lower bounds for each operation.

We consider the representational state complexity of unranked tree automata.
The bottom-up computation of an unranked tree automaton may be either
deterministic or nondeterministic, and further variants arise depending on
whether the horizontal string languages defining the transitions are
represented by a DFA or an NFA. Also, we consider for unranked tree automata
the alternative syntactic definition of determinism introduced by Cristau et
al. (FCT'05, Lect. Notes Comput. Sci. 3623, pp. 68-79).

Recently, the problem of obtaining a short regular expression equivalent to a
given finite automaton has been intensively investigated. Algorithms for
converting finite automata to regular expressions have an exponential blow-up
in the worst-case. To overcome this, simple heuristic methods have been
proposed.

In this paper we analyse some of the heuristics presented in the literature
and propose new ones. We also present some experimental comparative results
based on uniform random generated deterministic finite automata.

One of the theoretical models proposed for the mechanism of gene unscrambling
in some species of ciliates is the template-guided recombination (TGR) system
by Prescott, Ehrenfeucht and Rozenberg which has been generalized by Daley and
McQuillan from a formal language theory perspective. In this paper, we propose
a refinement of this model that generates regular languages using the iterated
TGR system with a finite initial language and a finite set of templates, using
fewer templates and a smaller alphabet compared to that of the Daley-McQuillan
model.

In this article, we consider the operations of insertion and deletion working
in a graph-controlled manner. We show that like in the case of context-free
productions, the computational power is strictly increased when using a control
graph: computational completeness can be obtained by systems with insertion or
deletion rules involving at most two symbols in a contextual or in a
context-free manner and with the control graph having only four nodes.

This paper is a continuation of our research work on state complexity of
combined operations. Motivated by applications, we study the state complexities
of two particular combined operations: catenation combined with star and
catenation combined with reversal. We show that the state complexities of both
of these combined operations are considerably less than the compositions of the
state complexities of their individual participating operations.

We investigate the magic number problem, that is, the question whether there
exists a minimal n-state nondeterministic finite automaton (NFA) whose
equivalent minimal deterministic finite automaton (DFA) has alpha states, for
all n and alpha satisfying n less or equal to alpha less or equal to exp(2,n).
A number alpha not satisfying this condition is called a magic number (for n).
It was shown in [11] that no magic numbers exist for general regular languages,
while in [5] trivial and non-trivial magic numbers for unary regular languages
were identified.

Currently there is great interest in computational models consisting of
underlying regular computational environments, and built on them distributed
computational structures. Examples of such models are cellular automata,
spatial computation and space-time crystallography. For any computational model
it is natural to define a functional equivalence of different but related
computational structures.

In this report we study the problem of minimising deterministic automata over
finite and infinite words. Deterministic finite automata are the simplest
devices to recognise regular languages, and deterministic Buchi, Co-Buchi, and
parity automata play a similar role in the recognition of \omega-regular
languages. While it is well known that the minimisation of deterministic finite
and weak automata is cheap, the complexity of minimising deterministic Buchi
and parity automata has remained an open challenge. We establish the
NP-completeness of these problems.

Let $\mathcal{P}(\Sigma^*)$ be the semiring of languages, and consider its
subset $\mathcal{P}(\Sigma)$. In this paper we define the language recognized
by a weighted automaton over $\mathcal{P}(\Sigma)$ and a one-letter alphabet.
Similarly, we introduce the notion of language recognition by linear recurrence
equations with coefficients in $\mathcal{P}(\Sigma)$. We will see that these
two definitions coincide.

We study time-bounded reachability in continuous-time Markov decision
processes for time-abstract scheduler classes. Such reachability problems play
a paramount role in dependability analysis and the modelling of manufacturing
and queueing systems. Consequently, their analysis has been studied
intensively, and techniques for the approximation of optimal control are well
understood. From a mathematical point of view, however, the question of
approximation is secondary compared to the fundamental question whether or not
optimal control exists.

In this paper we extend the work on \emph{dynamic ob\-servers} for fault
diagnosis to timed automata. We study sensor minimization problems with static
observers and then address the problem of computing the most permissive dynamic
observer for a system given by a timed automaton.

In this paper, following the way opened by a previous paper deposited on
arXiv, we give an upper bound to the number of states for a hyperbolic cellular
automaton in the pentagrid. Indeed, we prove that there is a hyperbolic
cellular automaton which is rotation invariant and whose halting problem is
undecidable and which has 9~states.

In this paper, we show a construction of a weakly universal cellular
automaton in the 3D hyperbolic space with two states. The cellular automaton is
rotation invariant and, moreover, based on a new implementation of a railway
circuit in the dodecagrid,the construction is a truly 3D-one.

We prove the Cerny conjecture for one-cluster automata with prime length
cycle. Consequences are given for the hybrid Road-coloring-Cerny conjecture for
digraphs with a proper cycle of prime length.

This paper solves an open problem concerning the generative power of
nonerasing context-free rewriting systems using a simple mechanism for checking
for context dependencies, in the literature known as semi-conditional grammars
of degree (1,1). In these grammars, two nonterminal symbols are attached to
each context-free production, and such a production is applicable if one of the
two attached symbols occurs in the current sentential form, while the other
does not.

In this paper we study the fault codiagnosis problem for discrete event
systems given by finite automata (FA) and timed systems given by timed automata
(TA). We provide a uniform characterization of codiagnosability for FA and TA
which extends the necessary and sufficient condition that characterizes
diagnosability. We also settle the complexity of the codiagnosability problems
both for FA and TA and show that codiagnosability is PSPACE-complete in both
cases. For FA this improves on the previously known bound (EXPTIME) and for TA
it is a new result.

A regular language L is said to be cellular if there exists a 1-dimensional
cellular automaton CA such that L is the language consisting of the finite
blocks associated with CA. It is shown that cellularity of a regular language
is decidable using a new characterization of cellular languages formulated by
Freiling, Goldstein and Moews and implied by a deep result of Boyle in symbolic
dynamics.

We prove that there exists no algorithm to decide whether the language
generated by a context-free grammar is dense with respect to the lexicographic
ordering. As a corollary to this result, we show that it is undecidable whether
the lexicographic orderings of the languages generated by two context-free
grammars have the same order type.

We consider Parikh images of languages accepted by non-deterministic finite
automata and context-free grammars; in other words, we treat the languages in a
commutative way --- we do not care about the order of letters in the accepted
word, but rather how many times each one of them appears. In most cases we
assume that the alphabet is of fixed size. We show tight complexity bounds for
problems like membership, equivalence, and disjointness.

This paper illustrates a technique for specifying the detailed timing,
logical operation, and compositional circuit design of digital circuits in
terms of ordinary state machines with output (transducers). The method is
illustrated here with specifications of gates, latches, and other simple
circuits and via the construction of devices starting with a SR latch built
from gates and then moving on to more complex devices. Circuit timing and
transients are treated in some detail. The method is based on "classical"
automata and recursive functions on strings.

We propose an algorithm that test membership for regular expressions and show
that the algorithm is correct. This algorithm is written in the style of a
sequent proof system. The advantage of this algorithm over traditional ones is
that the complex conversion process from regular expressions to finite automata
is not needed. As a consequence, our algorithm is simple and extends easily to
various extensions to regular expressions such as timed regular expressions or
regular languages with the intersection.

An algebraic linear ordering is a component of the initial solution of a
first-order recursion scheme over the continuous categorical algebra of
countable linear orderings equipped with the sum operation and the constant 1.
Due to a general Mezei-Wright type result, algebraic linear orderings are
exactly those isomorphic to the linear ordering of the leaves of an algebraic
tree.

An algebraic tree T is one determined by a finite system of fixed point
equations. The frontier \Fr(T) of an algebraic tree t is linearly ordered by
the lexicographic order \lex. When (\Fr(T),\lex) is well-ordered, its order
type is an \textbf{algebraic ordinal}. We prove that the algebraic ordinals are
exactly the ordinals less than $\omega^{\omega^\omega}$.

Systems of equations with sets of integers as unknowns are considered. It is
shown that the class of sets representable by unique solutions of equations
using the operations of union and addition $S+T=\makeset{m+n}{m \in S, \: n \in
T}$ and with ultimately periodic constants is exactly the class of
hyper-arithmetical sets. Equations using addition only can represent every
hyper-arithmetical set under a simple encoding.

A new approach to the design of massively parallel and interactive
programming languages has been recently proposed using rv-systems (interactive
systems with registers and voices) and Agapia programming. In this paper we
present a few theoretical results on FISs (finite interactive systems), the
underlying mechanism used for specifying control and interaction in these
systems. First, we give a proof for the undecidability of the emptiness problem
for FISs, by reduction to the Post Correspondence Problem.

A language L is prefix-closed if, whenever a word w is in L, then every
prefix of w is also in L. We define suffix-, factor-, and subword-closed
languages in the same way, where by subword we mean subsequence. We study the
quotient complexity (usually called state complexity) of operations on prefix-,
suffix-, factor-, and subword-closed languages.

Visibly pushdown automata (VPA), introduced by Alur and Madhusuan in 2004, is
a subclass of pushdown automata whose stack behavior is completely determined
by the input symbol according to a fixed partition of the input alphabet. Since
its introduce, VPAs have been shown to be useful in various context, e.g., as
specification formalism for verification and as automaton model for processing
XML streams. Due to high complexity, however, implementation of formal
verification based on VPA framework is a challenge.

Motivated by questions in biology and distributed computing, we investigate
the behaviour of particular cellular automata, modelled as one-dimensional
arrays of identical finite automata. We investigate what sort of
self-stabilising cooperative behaviour these can induce in terms of waves of
cellular state changes along a filament of cells. We discover what the minimum
requirements are, in terms of numbers of states and the range of communication
between automata, to observe this for individual filaments.

Repetition avoidance has been studied since Thue's work. In this paper, we
considered another type of repetition, which is called pseudo-power. This
concept is inspired by Watson-Crick complementarity in DNA sequence and is
defined over an antimorphic involution $\phi$. We first classify the alphabet
$\Sigma$ and the antimorphic involution $\phi$, under which there exists
sufficiently long pseudo-$k$th-power-free words. Then we present algorithms to
test whether a finite word $w$ is pseudo-$k$th-power-free.

We introduce a natural language interface for building stochastic pi calculus
models of biological systems. In this language, complex constructs describing
biochemical events are built from basic primitives of association, dissociation
and transformation. This language thus allows us to model biochemical systems
modularly by describing their dynamics in a narrative-style language, while
making amendments, refinements and extensions on the models easy. We
demonstrate the language on a model of Fc-gamma receptor phosphorylation during
phagocytosis.

A language L over a finite alphabet is growth-sensitive (or entropy
sensitive) if forbidding any set of subwords F yields a sub-language L^F whose
exponential growth rate (entropy) is smaller than that of L. Let (X, E, l) be
an infinite, oriented, labelled graph. Considering the graph as an (infinite)
automaton, we associate with any pair of vertices x,y in X the language
consisting of all words that can be read as the labels along some path from x
to y. Under suitable, general assumptions we prove that these languages are
growth-sensitive.

We consider some questions about formal languages that arise when inverses of
letters, words and languages are defined. The reduced representation of a
language over the free monoid is its unique equivalent representation in the
free group. We show that the class of regular languages is closed under taking
the reduced representation, while the class of context-free languages is not.
We also give an upper bound on the state complexity of the reduced
representation of a regular language, and prove upper and lower bounds on the
length of the shortest reducible string in a regular language.

Macro tree transducers (mtts) are a useful formal model for XML query and
transformation languages. In this paper one of the fundamental decision
problems on translations, namely the "translation membership problem" is
studied for mtts. For a fixed translation, the translation membership problem
asks whether a given input/output pair is element of the translation. For
call-by-name mtts this problem is shown to be NP-complete. The main result is
that translation membership for call-by-value mtts is in polynomial time.

The results of several papers concerning the \v{C}ern\'y 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.

The famous \v{C}ern\'y conjecture claims that each $n$-state synchronizing
automaton $\mathrsfs{A}$ has a reset word of length at most $(n-1)^2$. The best
upper bound for the minimum length of reset word for $\mathrsfs{A}$ known so
far is a cubic polynomial of $n$. So the problem of searching length of a
shortest word is of certain importance. This problem is $NP$-complete. However,
the algorithmic problem of approximation length of a minimal reset word is
still open. Gawrychowski proved that this problem is $NP$-complete for the
error 2.