Language and Automata Theory and Applications

Timed automata and timed languages [1] constitute a beautiful discovery that opened new perspectives to automata and language theory, as well as new applications to computer-aided verification. However the theory of timed regular languages is far from being achieved. Seven years ago, in [2], I argued that developing such a theory constituted an important research challenge, and I sketched a research program in this direction. Unfortunately, when listing research tasks on timed languages I have overlooked one interesting topic: measuring size of and information content in such languages. Catching up this omission became the focus of my research and the theme of this talk.

This work describes a data structure, the

Implicit Real-Vector Automaton (IRVA)

, suited for representing symbolically polyhedra, i.e., regions of

n

-dimensional space defined by finite Boolean combinations of linear inequalities. IRVA can represent exactly arbitrary convex and non-convex polyhedra, including features such as open and closed boundaries, unconnected parts, and non-manifold components. In addition, they provide efficient procedures for deciding whether a point belongs to a given polyhedron, and determining the polyhedron component (vertex, edge, facet, …) that contains a point. An advantage of IRVA is that they can easily be minimized into a canonical form, which leads to a simple and efficient test for equality between represented polyhedra. We also develop an algorithm for computing Boolean combinations of polyhedra represented by IRVA.

The physical Church-Turing thesis explains the Galileo thesis, but also suggests an evolution of the language used to describe nature. It can be proved from more basic principle of physics, but it also questions these principles, putting the emphasis on the principle of a bounded density of information. This principle itself questions our formulation of quantum theory, in particular the choice of a field for the scalars and the origin of the infinite dimension of the vector spaces used as state spaces.

The article was prepared for the LATA 2012 conference where I will be presenting two one and half hour lectures for a short tutorial on parameterized complexity. Much fuller accounts can be found in the books Downey-Fellows [33, 34], Niedermeier [72], Flum-Grohe [49], the two issues of the

Computer Journal

[36] and the recent survey Downey-Thilikos [39].

DNA nanotechnology, pioneered by Seeman, Winfree, and Rothemund, exploits the information processing capabilities of nucleic acids to

program matter

to do our bidding at atomic and molecular scales. This field is now a rapidly growing interdisciplinary research adventure involving chemists, molecular biologists, computer scientists, materials scientists, electrical and computer engineers, and others. DNA tile assembly, DNA origami, and DNA strand displacement have enabled the programmed self-assembly of complex nanoscale structures, dynamic nanoscale machines, and nanoscale Boolean circuits. Applications on the horizon include patterning of smaller, faster computer chips; nanoscale detectors and instruments for measurement; and in-cell computers that diagnose and treat disease. This talk will survey the role of computer science in making DNA nanotechnology more productive, predictable, and safe. Topics will include the specification and verification of nanoscale systems, the intrinsic universality (a strong version of Turing universality) of self-assembly, the role of randomness in molecular programming, and the essential role of software in the

design

of wet-lab experiments in DNA nanotechnology.

This paper introduces the model of

priced timed pushdown systems

as an extension of discrete-timed pushdown systems with a cost model that assigns multidimensional costs to both transitions and stack symbols. For this model, we consider the minimal cost reachability problem: i.e., given a priced timed pushdown system and a target set of configurations, determine the minimal possible cost of any run from the initial to a target configuration. We solve the problem by reducing it to the reachability problem in standard pushdown systems.

We model chaining in terms of a simple, convergent, rewrite system over a signature with two disjoint sorts:

list

and

element.

By interpreting a particular symbol of this signature suitably, the rewrite system can model several practical situations of interest. An inference procedure is presented for deciding the unification problem modulo this rewrite system. The procedure is modular in the following sense: any given problem is handled by a system of ‘list-inferences’, and the set of equations thus derived between the element-terms of the problem is then handed over to any (‘black-box’) procedure which is complete for solving these element-equations. An example of application of this unification procedure is given, as attack detection on a Needham-Schroeder like protocol employing the CBC encryption mode.

Given two

n

-variable Boolean functions

f

and

g

, we study the problem of computing an

ε-approximate isomorphism

between them. I.e. a permutation

π

of the

n

variables such that

f

(

x

1

,

x

2

,…,

x

n

) and

g

(

x

π

(1)

,

x

π

(2)

,…,

x

π

(

n

)

) differ on at most an

ε

fraction of all Boolean inputs {0,1}

n

. We give a randomized

$2^{O(\sqrt{n}polylog(n))}$

algorithm that computes a

$\frac{1}{2^{polylog(n)}}$

-approximate isomorphism between two isomorphic Boolean functions

f

and

g

that are given by depth

d

circuits of poly(

n

) size, where

d

is a constant independent of

n

. In contrast, the best known algorithm for computing an

exact isomorphism

between

n

-ary Boolean functions has running time 2

O

(

n

)

[9] even for functions computed by poly(

n

) size DNF formulas. Our algorithm is based on a result for hypergraph isomorphism with bounded edge size [3] and the classical Linial-Mansour-Nisan result on approximating small depth and size Boolean circuits by small degree polynomials using Fourier analysis.

Deterministic and non-deterministic multi-head finite automata are known to characterize the deterministic and non- deterministic logarithmic space complexity classes, respectively. Recently, Morita introduced

reversible

multi-head finite automata (RMFAs), and posed the question of whether RMFAs characterize reversible logarithmic space as well. Here, we resolve the question affirmatively, by exhibiting a clean RMFA simulation of logarithmic space reversible Turing machines. Indirectly, this also proves that reversible and deterministic multi-head finite automata recognize the same languages.

Conjunctive grammars (Okhotin, 2001) are an extension of the standard context-free grammars with a conjunction operation, which maintains most of their practical properties, including many parsing algorithms. This paper introduces a further extension to the model, which is equipped with quantifiers for referring to the left context, in which the substring being defined does occur. For example, a rule

$A \rightarrow a \& \triangleleft{B}$

defines a string

a

, as long as it is preceded by any string defined by

B

. The paper gives two equivalent definitions of the model—by logical deduction and by language equations—and establishes its basic properties, including a transformation to a normal form, a cubic-time parsing algorithm, and another recognition algorithm working in linear space.

The

longest common extension

(LCE) problem is to preprocess a string in order to allow for a large number of LCE queries, such that the queries are efficient. The LCE value,

LCE

s

(

i

,

j

), is the length of the longest common prefix of the pair of suffixes starting at index

i

and

j

in the string

s

. The LCE problem can be solved in linear space with constant query time and a preprocessing of sorting complexity. There are two known approaches achieving these bounds, which use nearest common ancestors and range minimum queries, respectively. However, in practice a much simpler approach with linear query time, no extra space and no preprocessing achieves significantly better average case performance. We show a new algorithm, F

ingerprint

k

, which for a parameter

k

, 1 ≤ 

k

 ≤ ⌈

log

n

⌉, on a string of length

n

and alphabet size

σ

, gives

O

(

k

n

1/

k

) query time using

O

(

k

n

) space and

O

(

k

n

 + 

sort

(

n

,

σ

)) preprocessing time, where

sort

(

n

,

σ

) is the time it takes to sort

n

numbers from

σ

. Though this solution is asymptotically strictly worse than the asymptotically best previously known algorithms, it outperforms them in practice in average case and is almost as fast as the simple linear time algorithm. On worst case input, this new algorithm is significantly faster in practice compared to the simple linear time algorithm. We also look at cache performance of the new algorithm, and we show that for

k

 = 2, cache optimization can improve practical query time.

String comparison such as sequence alignment, edit distance computation, longest common subsequence computation, and approximate string matching is a key task (and often computational bottleneck) in large-scale textual information retrieval. For instance, algorithms for sequence alignment are widely used in bioinformatics to compare DNA and protein sequences. These problems can all be solved using essentially the same dynamic programming scheme over a two-dimensional matrix, where each entry depends locally on at most 3 neighboring entries. We present a simple, fast, and cache-oblivious algorithm for this type of local dynamic programming suitable for comparing large-scale strings. Our algorithm outperforms the previous state-of-the-art solutions. Surprisingly, our new simple algorithm is competitive with a complicated, optimized, and tuned implementation of the best cache-aware algorithm. Additionally, our new algorithm generalizes the best known theoretical complexity trade-offs for the problem.

The maximal matching problem, i.e., the computation of a matching that is not a proper subset of another matching, is a fundamental optimization problem and algorithms for maximal matchings have been used as submodules for problems like maximal node-disjoint paths or maximum flow. Since in some applications graphs become larger and larger, a research branch has emerged which is concerned with the design and analysis of implicit algorithms for classical graph problems. Input graphs are given as characteristic Boolean functions of their edge sets and problems have to be solved by functional operations. As OBDDs, which are closely related to deterministic finite automata, are a well-known data structure for Boolean functions, OBDD-based algorithms are used as a heuristic approach to handle very large graphs. Here, an implicit OBDD-based maximal matching algorithm is presented that uses only a polylogarithmic number of functional operations with respect to the number of vertices of the input graph.

We address termination analysis for the class of

gap-order constraint systems

(

GCS

), an (infinitely-branching) abstract model of counter machines recently introduced in [8], in which constraints (over ℤ) between the variables of the source state and the target state of a transition are

gap-order constraints

(

GC

) [18].

GCS

extend monotonicity constraint systems [4], integral relation automata [9], and constraint automata in [12]. Since

GCS

are infinitely-branching, termination does not imply

strong termination

, i.e. the existence of an upper bound on the lengths of the runs from a given state. We show the following: (1) checking strong termination for

GCS

is decidable and P

space

-complete, and (2) for each control location of the given

GCS

, one can build a

GC

representation of the set of variable valuations from which strong termination does

not

hold.

This paper studies how one can spread points in the Besicovitch space in order to keep them far one from another. We first study the general case and then what happens if the chosen points are all regular Toeplitz configurations or all quasiperiodic configurations.

Several studies have been achieved to construct a finite automaton that recognizes the set of words that are at a bounded distance from some word of a given language. In this paper, we introduce a new family of regular operators based on a generalization of the notion of distance and we define a new family of expressions, the

approximate regular expressions

. We compute Brzozowski derivatives and Antimirov derivatives of such operators, which allows us to provide two recognizers for the language denoted by any approximate regular expression.

In this paper we introduce a class of Petri nets, called

catalytic Petri nets

, and a suitable firing strategy where transitions are fired only when they use tokens from specific places, called catalytic places. By establishing a one-to-one relationship with

catalytic membrane systems

, we can prove that the class of catalytic Petri nets with at least two catalytic places is Turing complete.

ν

-CA are cellular automata which can have different local rules at each site of their lattice. Indeed, the spatial distribution of local rules completely characterizes

ν

-CA. In this paper, sets of distributions sharing some interesting properties are associated with languages of bi-infinite words. The complexity classes of these languages are investigated providing an initial rough classification of

ν

-CA.

The notion of recognition of a language by a finite semigroup can be generalized to recognition by finite groupoids, i.e. sets equipped with a binary operation ‘·’ which is not necessarily associative. It is well known that

L

can be recognized by a groupoid iff

L

is context-free. But it is also known that some subclasses of groupoids can only recognize regular languages. For example,

loops

recognize exactly the regular open languages and Beaudry et al. described the largest class of groupoids known to recognize only regular languages.

A groupoid

H

is said to be

conservative

if a·b is in {

a

,

b

} for all

a

,

b

in

H

. The main result of this paper is that conservative groupoids can only recognize regular languages. This class is incomparable with the one of Beaudry et al. so we are exhibiting a new sense in which a groupoid can be too weak to have context-free capabilities.

In online graph coloring a graph is revealed to an online algorithm one vertex at a time, and the algorithm must color the vertices as they appear. This paper starts to investigate the advice complexity of this problem – the amount of oracle information an online algorithm needs in order to make optimal choices. We also consider a more general problem – a trade-off between online and offline graph coloring.

In the paper we prove that precisely ⌈

n

/2 ⌉ − 1 bits of advice are needed when the vertices on a path are presented for coloring in arbitrary order. The same holds in the more general case when just a subset of the vertices is colored online. However, the problem turns out to be non-trivial for the case where the online algorithm is guaranteed that the vertices it receives form a subset of a path and are presented in the order in which they lie on the path. For this variant we prove that its advice complexity is

βn

 + 

O

(log

n

) bits, where

β

 ≈ 0.406 is a fixed constant (we give its closed form). This suggests that the generalized problem will be challenging for more complex graph classes.

To store and search genomic databases efficiently, researchers have recently started building compressed self-indexes based on straight-line programs and LZ77. In this paper we show how, given a balanced straight-line program for a string

S

[1..n] whose LZ77 parse consists of

z

phrases, we can add

$\mathcal{O}{z log log z}$

words and obtain a compressed self-index for

S

such that, given a pattern

P

[1..

m

], we can list the occ occurrences of

P

in

S

in

$\mathcal{O}({m^{2} + (m + occ) log log n})$

time. All previous self-indexes are either larger or slower in the worst case.

The object of investigation in this paper is the learnability of co-recursively enumerable (co-r.e.) languages based on Gold’s [11] original model of inductive inference. In particular, the following learning models are studied: finite learning, explanatory learning, vacillatory learning and behaviourally correct learning. The relative effects of imposing further learning constraints, such as conservativeness and prudence on these various learning models are also investigated. Moreover, an extension of Angluin’s [1] characterisation of identifiable indexed families of recursive languages to families of conservatively learnable co-r.e. classes is presented. In this connection, the paper considers the learnability of indexed families of recursive languages, uniformly co-r.e. classes as well as other general classes of co-r.e. languages. A containment hierarchy of co-r.e. learning models is thereby established; while this hierarchy is quite similar to its r.e. analogue, there are some surprising collapses when using a co-r.e. hypothesis space; for example vacillatory learning collapses to explanatory learning.

The question of the state-size cost for simulation of two-way nondeterministic automata (2

nfas

) by two-way deterministic automata (2

dfas

) was raised in 1978 and, despite many attempts, it is still open. Subsequently, the problem was attacked by restricting the power of 2

dfas

(e.g., using a restricted input head movement) to the degree for which it was already possible to derive some exponential gaps between the weaker model and the standard 2

nfas

. Here we use an opposite approach, increasing the power of 2

dfas

to the degree for which it is still possible to obtain a subexponential conversion from the stronger model to the standard 2

dfas

. In particular, it turns out that subexponential conversion is possible for two-way automata that make nondeterministic choices only when the input head scans one of the input tape endmarkers. However, there is no restriction on the input head movement. This implies that an exponential gap between 2

nfas

and 2

dfas

can be obtained only for unrestricted 2

nfas

using capabilities beyond the proposed new model.

As an additional bonus, conversion into a machine for the complement of the original language is polynomial in this model. The same holds for making such machines self-verifying, halting, or unambiguous. Finally, any superpolynomial lower bound for the simulation of such machines by standard 2

dfas

would imply

L

 ≠ 

NL

. In the same way, the alternating version of these machines is related to L ≟ NL ≟ P, the classical computational complexity problems.

This article proposes polynomial-time algorithms for learning typed pattern languages—formal languages that are generated by patterns consisting of terminal symbols and typed variables. A string is generated by a typed pattern by substituting all variables with strings of terminal symbols that belong to the corresponding types.

The algorithms presented consitute non-trivial generalizations of Lange and Wiehagen’s efficient algorithm for learning patterns in which variables are not typed. This is achieved by defining

type witnesses

to impose structural conditions on the types used in the patterns. It is shown that Lange and Wiehagen’s algorithm implicitly uses a special case of type witnesses. Moreover, the type witnesses for a typed pattern form characteristic sets whose size is linear in the length of the pattern; our algorithm, when processing any set of positive data containing such a characteristic set, will always generate a typed pattern equivalent to the target pattern. Thus our algorithms are of relevance to the area of grammatical inference, in which such characteristic sets are typically studied.

This paper investigates ways to reduce redundancy in forbidding sets for language forbidding-enforcing systems. A language forbidding set disallows combinations of subwords in a word, while permitting the presence of some parts of these combinations. Since a forbidding set is a potentially infinite set of finite sets of words, finding normal forms for forbidding sets is interesting from a combinatorics on words perspective and important for the theoretical investigation of language fe-systems, the connection between variants of fe-systems, and their applications to molecular computation. This paper shows that the minimal normal forms for forbidding sets defining classes of languages (fe-families) are also normal forms for forbidding sets defining single languages (fe-languages), but not necessarily minimal. Thus, an investigation of minimality and sufficient conditions for fe-languages are presented and it is shown that in special cases they coincide with a minimal normal form for fe-families.

We introduce a new connection between formal language theory and proof theory. One of the most fundamental proof transformations in a class of formal proofs is shown to correspond exactly to the computation of the language of a certain class of tree grammars. Translations in both directions, from proofs to grammars and from grammars to proofs, are provided. This correspondence allows theoretical as well as practical applications.

We study the membership problem for regular expressions extended with operators for

unordered concatenation

and

numerical constraints

. The unordered concatenation of a set of regular expressions denotes all sequences consisting of exactly one word denoted by each of the expressions. Numerical constraints are an extension of regular expressions used in many applications, e.g. text search (e.g., UNIX grep), document formats (e.g. XML Schema). Regular expressions with unordered concatenation and numerical constraints denote the same languages as the classical regular expressions, but, in certain important cases, exponentially more succinct. We show that the membership problem for regular expressions with unordered concatenation (without numerical constraints) is already NP-hard. We show a polynomial-time algorithm for the membership problem for regular expressions with numerical constraints and unordered concatenation, when restricted to a subclass called

strongly 1-unambiguous

.

A

restarting transducer

is a restarting automaton that is equipped with an

output function

. Accordingly, restarting transducers compute binary relations, and deterministic restarting transducers compute functions. Here we characterize the

rational functions

and some of their proper subclasses by certain types of deterministic restarting transducers with window size one.

Given an

n

-tape automaton

M

with a one-way read-only head per tape which is delimited by an end marker $ and a nonnegative integer

k

, we say that

M

is weakly

k

-synchronized if for every

n

-tuple

x

 = (

x

1

, …,

x

n

) that is accepted, there is an accepting computation on

x

such that no pair of input heads, neither of which is on $, are more than

k

tape cells apart at any time during the computation. When a head reaches the marker, it can no longer move. As usual, an

n

-tuple

x

 = (

x

1

, …,

x

n

) is accepted if

M

eventually reaches the configuration where all

n

heads are on $ in an accepting state. We look at the following problems: (1) Given an

n

-tape automaton

M

, is it weakly

k

-synchronized for a given

k

(for some

k

)? and (2) Given an

n

-tape automaton

M

, does there exist a weakly

k

-synchronized automaton for a given

k

(for some

k

)

M

′ such that

L

(

M

′) = 

L

(

M

)? In an earlier paper [1], we studied the case of multitape finite automata (NFAs). Here, we investigate the case of multitape pushdown automata (NPDAs), multitape Turing machines, and other multitape models. The results that we obtain contrast those of the earlier results and involve some rather intricate constructions.

We introduce an automata model for data words, that is words that carry at each position a symbol from a finite alphabet and a value from an unbounded data domain. The model is (semantically) a restriction of data automata, introduced by Bojanczyk, et. al. in 2006, therefore it is called

weak data automata

. It is strictly less expressive than data automata and the expressive power is incomparable with register automata. The expressive power of weak data automata corresponds exactly to existential monadic second order logic with successor + 1 and data value equality ~, EMSO

2

( + 1,~). It follows from previous work, David, et. al. in 2010, that the nonemptiness problem for weak data automata can be decided in 2-

NEXPTIME

. Furthermore, we study weak Büchi automata on data

ω

-strings. They can be characterized by the extension of EMSO

2

( + 1,~) with existential quantifiers for infinite sets. Finally, the same complexity bound for its nonemptiness problem is established by a nondeterministic polynomial time reduction to the nonemptiness problem of weak data automata.

Concurrent game structures model multi-player games played on finite graphs where the players simultaneously choose their moves and collectively determine the next state of the game. We extend this model with prices on transitions for each player. We study pure Nash equilibria in this framework where each player’s payoff is the accumulated price of all transitions until reaching their goal state. We provide a construction of a Büchi automaton accepting all Nash equilibria outcomes and show how this construction can be used to solve a variety of related problems, such as finding pareto-optimal equilibria. Furthermore, we prove the problem of deciding the existence of equilibria to be NP-complete.

Computing by Observing is a theoretical model for computation that tries to formalize the standard setup of experiments in natural sciences. We establish that insertion systems with empty contexts and only one inserted letter suffice in this architecture to accept all recursively enumerable languages. While so far in most cases context-free power was needed, here a sub-regular system leads to computational completeness in this context. Further, we investigate more complicated insertion systems in a model with less powerful observer called Observing Change.

We investigate the application of Courcelle’s Theorem and the logspace version of Elberfeld et al. in the context of the implication problem for propositional sets of formulae, the extension existence problem for default logic, as well as the expansion existence problem for autoepistemic logic and obtain fixed-parameter time and space efficient algorithms for these problems.

On the other hand, we exhibit, for each of the above problems, families of instances of a very simple structure that, for a wide range of different parameterizations, do not have efficient fixed-parameter algorithms (even in the sense of the large class XP

nu

), unless P=NP.

We show that there are Cayley graph automatic groups that are not Cayley graph biautomatic. In addition, we show that there are Cayley graph automatic groups with undecidable Conjugacy Problem and that the Isomorphism Problem is undecidable in the class of Cayley graph automatic groups.

In this paper we improve our previous work by introducing

optimized on-the-fly

algorithms to test universality and inclusion problems of visibly pushdown automata. We implement the proposed algorithms in a prototype tool. We conduct experiments on randomly generated VPA. The experimental results show that the proposed method outperforms the standard one by several orders of magnitude.

We define an automaton-based abstract interpretation of a trace semantics which identifies loops that definitely initialize all the elements of an array, a useful piece of information for the static analysis of imperative languages. This results in a fully automatic and fast analysis, that does not use manual code annotations. Its implementation inside the Julia analyzer is efficient and precise.

This paper presents a combinatorial study to characterise the dynamics of intersecting Boolean automata circuits and more specifically that of

double Boolean automata circuits

. Explicit formulae are given to count the number of periodic configurations and attractors of these networks and a conjecture proposes a comparison between the number of attractors of isolated circuits and that of double circuits. The aim of this study is to give intuition on the way circuits interact and how a circuits intersection modifies the “degrees of freedom” of the overall network.

In a previous work we introduced slice graphs as a way to specify both infinite languages of directed acyclic graphs (DAGs) and infinite languages of partial orders. Therein we focused on the study of Hasse diagram generators, i.e., slice graphs that generate only transitive reduced DAGs. In the present work we show that any slice graph can be transitive reduced into a Hasse diagram generator representing the same set of partial orders. This result allow us to establish unknown connections between the true concurrent behavior of bounded

p

/

t

-nets and traditional approaches for representing infinite families of partial orders, such as Mazurkiewicz trace languages and Message Sequence Chart (

MSC

) languages. Going further, we identify the family of weakly saturated slice graphs. The class of partial order languages which can be represented by weakly saturated slice graphs is closed under union, intersection and a suitable notion of complementation (bounded cut-width complementation). The partial order languages in this class also admit canonical representatives in terms of Hasse diagram generators, and have decidable inclusion and emptiness of intersection. Our transitive reduction algorithm plays a fundamental role in these decidability results.

We develop a necessary condition for ET0L languages inspired by Ogden’s Lemma. Besides being useful for proving that individual languages are not ET0L languages, this result also gives an alternative proof of Ehrenfeucht and Rozenberg’s theorem about rare and nonfrequent symbols in ET0L languages.

We show that any parameter of patterns that is an upper bound for the treewidth of appropriate encodings of patterns as relational structures, if restricted to a constant, allows the membership problem for pattern languages to be solved in polynomial time. Furthermore, we identify a new such parameter, called the scope coincidence degree.

The parameterized Synchronizing-Road-Coloring Problem (in short: SRCP

$_C^\ell$

) in its decision version can be formulated as follows: given a digraph

G

with constant out-degree ℓ, check if

G

can be synchronized by some word of length

C

for some synchronizing labeling. We consider the family

$\{SRCP_C^\ell\}_{C,\ell}$

of problems parameterized with constants

C

and ℓ and try to find for which

C

and ℓ SRCP

$_C^\ell$

is

NP

-complete. It is known that SRCP

$_C^3$

is

NP

-complete for

C

 ≥ 8. We improve this result by showing that it is so for

C

 ≥ 4 and for ℓ ≥ 3. We also show that SRCP

$_C^\ell$

is in

P

for

C

 ≤ 2 and ℓ ≥ 1. Hence, we solve SRCP almost completely for alphabet with 3 or more letters. The case

C

 = 3 is still an open problem.

The notion of a

k

-automatic set of integers is well-studied. We develop a new notion — the

k

-automatic set of rational numbers — and prove basic properties of these sets, including closure properties and decidability.

In this paper, we define the notion of limit set for a finite family of cellular automata, which is a generalization of the limit set of a single automaton. We prove that the hierarchy formed by increasing the number of automata in the defining set is infinite, and study the boolean closure properties of different classes of limit sets.

Given a group

G

and a positive integer

d

 ≥ 2 we introduce the notion of an automaton rank of a group

G

with respect to its self-similar actions on a

d

-ary tree of words as the minimal number of states in an automaton over a

d

-letter alphabet which generates this group (topologically if

G

is closed). We construct minimal automata generating free abelian groups of finite ranks, which completely determines automaton ranks of free abelian groups. We also provide naturally defined 3-state automaton realizations for profinite groups which are infinite wreath powers … ≀ 

H

 ≀ 

H

for some 2-generated finite perfect groups

H

. This determines the topological rank and improves the estimation for the automaton rank of these wreath powers. We show that we may take

H

as alternating groups and projective special linear groups.

We examine characteristic features of reversible and quantum computations in the presence of supplementary information, known as advice. In particular, we present a simple, algebraic characterization of languages recognized by one-way reversible finite automata with advice. With a further elaborate argument, a similar but slightly weaker result for bounded-error one-way quantum finite automata is also proven. As an immediate application of those features, we demonstrate certain containments and separations among various standard language families that are suitably assisted by advice.

Recently several “distributional learning algorithms” have been proposed and have made great success in learning different subclasses of context-free grammars. The distributional learning models and exploits the relation between strings and contexts that form grammatical sentences in the language of the learning target. There are two main approaches. One, which we call

primal

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

dual

, uses contexts to characterize the language of each nonterminal of the conjecture grammar. This paper shows how those opposite approaches are integrated into single learning algorithms that learn quite rich classes of context-free grammars.