
\documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty}
\textwidth=3D12.8cm
\textheight=3D21.7cm
\hoffset=3D-0.3in
\voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt
%------------------------------------------------------------
\begin{document}
\baselineskip=3D15pt

\centerline{\large \bf Sturmian pseudowords}

\bigskip

\centerline{Jorge Almeida}
\centerline{\it Universidade do Porto, Portugal}
\centerline{e-mail {\tt jalmeida@fc.up.pt}}

\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
\par

Relatively free profinite semigroups play an important role in the
theory of finite semigroups. Their elements may be viewed as implicit
operations and this operational point of view has led to many
important applications. It has also suggested the exploration of
methods from symbolic dynamics to investigate profinite semigroups.
Viewing the elements of finitely generated relatively free profinite
semigroups as combinatorial objects generalizing semigroup words on a
finite alphabet, following M. V. Volkov they are also called
\emph{pseudowords}. In this work, pseudowords of low complexity $q(n)$
are considered, where $q(n)$ denotes the number of factors of
length~$n$ of the pseudoword. The lowest possible complexity for
pseudowords which are not almost periodic is $q(n)=3Dn+1$ and this bound
can only be attained on a two-letter alphabet. A pseudoword is
\emph{Sturmian} if it has this minimal complexity and further its
finite factors can be found within bounded distance from both its
ends. Using classical invariants from the theory of Sturmian infinite
words, it is possible to draw several conclusions on the structure of
the $\mathcal J$-classes of Sturmian pseudowords. In particular, the
$\mathcal J$-maximal Sturmian pseudowords form uncountably many
$\mathcal J$-classes, which are Brandt groupoids.

\end{document}
___________________________________________
\documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty}
\textwidth=3D12.8cm
\textheight=3D21.7cm
\hoffset=3D-0.3in
\voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt
%------------------------------------------------------------
\begin{document}
\baselineskip=3D15pt

\centerline{\large \bf Balanced Grammars and Their Languages}

\bigskip

\centerline{Jean Berstel}
\centerline{\it Universit\'e de Marne-la-Vall\'ee, France}
\centerline{e-mail {\tt berstel@univ-mlv.fr}}

%%% in case of several authors:
\smallskip
\centerline{Luc Boasson}
\centerline{\it Universit\'e Denis-Diderot, France}
\centerline{e-mail {\tt boasson@liafa.jussieu.fr}}
%%%

\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
\par
%   Text of the abstract
Balanced grammars are extended context-free grammars of a special
kind. They generate words=20
over a set of parenthesis that are well-formed (i.e. Dyck words).  The
right-hand side of any production of a balanced grammar is well-formed
in a sense to be described. Moreover, for each nonterminal, the set of
right-hand sides of productions for this nonterminal is a regular set.

The motivation for studying balanced grammars is twofold. First, it
appears that grammars describing XML-documents are special cases of
balanced grammars. The
syntactic properties of these grammars have been considered earlier by
the authors. Next, parenthesis grammars, as
developed by McNaughton and Knuth,
also appear to be=20
balanced grammars, but with finitely many productions and only one
pair of parentheses.
Parenthesis grammars have many interesting syntactic and decision
properties, and it is interesting to investigate whether these
properties carry over to grammars with regular sets of productions and
several pairs of parentheses.

A context-free grammar will be called \textit{regular} if, for each
nonterminal, the set of right-hand sides of productions for this
nonterminal is regular. The case of usual
context-free grammars is when this set is finite.
Extending the
set of productions does not change the family of languages that is
generated.=20

We prove that every (regular) grammar can be converted to a
codeterministic grammar. This was proved by McNaughton in the case of
parenthesis grammars. Then, we give undecidability results for
balanced languages. It is shown that every codeterministic balanced
grammar can be reduced to a minimal balanced grammar, and that this
grammar is unique. We show that balanced languages are closed under
complement. This is a result that does not hold within the framework of
parenthesis
grammars. A syntactic characterization of balanced
language is given next, by showing that these are well-formed languages
such that the set of Dyck
words intersects only a finite number of congruence classes for the
syntactic congruence of the language. Although this property is
undecidable, it is closely related to the decision procedure for=20
balanced languages with bounded width.
Indeed, we show that this property always holds in the case of bounded
width.  \bigskip

%%% in case of several authors:
{\bf  Presented by Jean Berstel}
%%%

\end{document}
_________________________________________________
\documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty} \textwidth=3D12.8cm \textheight=3D21.7cm
\hoffset=3D-0.3in \voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt

\begin{document}
\baselineskip=3D15pt


\centerline{\large \bf Minimal unsatisfiable $2$-CNF formulas }


\bigskip


%%% in case of several authors:
\smallskip
\centerline{Christian Choffrut and Ya\"el Haddad} \centerline{\it
LIAFA, Universit\'e Paris 7,  2, Pl. Jussieu
 75 251 Paris Cedex 05, France}
 \centerline{e-mail
{\tt Christian.Choffrut@liafa.jussieu.fr }}



\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
\par
%   Text of the abstract

A conjunction of clauses (a CNF formula) is unsatisfiable if there
exists no assignment to the variables that makes the conjunction
true. Furthermore, it is minimal unsatisfiable whenever the
removal of any of its clauses makes it satisfiable. The problem of
determining whether or not a given CNF is minimal unsatisfiable is
$DP$-complete where $DP$ represents all pairwise intersections of
a problem in NP and a problem in coNP. Recently, it was proved
that if the difference between the number of clauses and the
number of variables is fixed,  the problem becomes polynomial.

We investigate the simpler  case of $2$-CNF formulas (all clauses
are disjunctions of at most two literals)  whose unsatisfiability
problem is known to be complete in $NL$. We show that minimal
unsatisfiable $2$-CNF formulas with $n$ variables have at least
$n+1$ (which is well-known to hold for general CNF formulas) and
at most $2n$ clauses. We characterize those  minimal unsatifiable
$2$-CNF with maximal number of clauses. On the opposite direction,
i.e., looking for minimal unsatifiable $2$-CNF of minimal size, we
define a notion of simplification of $2$-CNF which allows us to
eliminate the variables occurring exactly once positively and
exactly once negatively and we show that there exists for all even
number of variables, say $2n$,
 a unique
 minimal unsatisfiable $2$-CNF with minimal
number of clauses (which happens to have
  $3n$ clauses).
Finally, we  give a linear time algorithm which decides whether or
not a given $2$-CNF is  minimal unsatisfiable.

\medskip


%%% in case of several authors:
{\bf  Presented by Christian Choffrut}
%%%

\end{document}
_____________________________________________

\documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty}
\textwidth=3D12.8cm
\textheight=3D21.7cm
\hoffset=3D-0.3in
\voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt
%------------------------------------------------------------
\begin{document}
\baselineskip=3D15pt

\documentclass{article}
\pagestyle{empty}
\textwidth
=3D12.8cm
\textheight=3D21.7cm
\hoffset=3D-0.3in

\begin{document}
\title{\Large\bf
Splicing Systems and Automata Theory \\
(Extended Abstract)
\thanks{Partially supported by $60 \%$ Project
{\it ``Linguaggi Formali e Modelli di Calcolo''}
(University of Salerno) and by {\bf MIUR} Project
{\it ``Linguaggi Formali e Automi: teoria ed applicazioni''}}}

\author{Paola Bonizzoni$~ ^\dag$,
Clelia De Felice$^{**}$,
Giancarlo
Mauri$~ ^\dag$, Rosalba Zizza
\thanks{
Dipartimento di Informatica Sistemistica e Comunicazione,
Universit\`a degli Studi di Milano -- Bicocca,
Via Bicocca degli Arcimboldi $8$, $20126$ Milano -- ITALY.
{\tt E-mail:\{bonizzoni,mauri,zizza\}@disco.unimib.it}
$\qquad $
$~ \quad ^{**}$
Dipartimento di Informatica ed Applicazioni,
Universit\`a di Salerno, 84081 Baronissi (SA) -- ITALY.
{\tt E-mail: defelice@unisa.it}.
}}

\date{}
\maketitle

%--------------------------------------------------

{\bf Introduction.}
Molecular Computing is a new branch connecting
Biology, Computer Science and Mathematics: the idea
is to look at=20
DNA molecules as a model of
computation where the operations are
performed by using enzymes and other biological
processes.
The rapid increase in interest
in Molecular Computing started
with Adleman's article (L. M. Adleman (1994),
Molecular computation of solutions to combinatorial problems,
{\it Science} {\bf 226}, $1021-1024$), where the author showed
how to solve
(a small instance of) the Hamiltonian Path Problem,
which is a NP-complete problem, by
manipulating DNA sequences in a lab.
The massive
parallelism performed by molecular operations in=20
the algorithm is the key element to its efficiency.
Thanks to this interest in Molecular Computing,
new models of computation have been suggested
and old ones have been reconsidered.
Indeed, in 1987 Tom Head pioneered
a language-theoretic approach for studying some
biological phenomena on DNA.
He introduced the formalism of=20
the {\em splicing
system} to observe the generative power of=20
some recombination processes. In this way,
abstract models for
the generated languages are defined
as a formal counterpart of the DNA recombination
under the reaction of
restriction and ligase enzymes: the (linear and
circular) Splicing Systems.
A splicing operation is introduced as an operator on strings,
inspired
by a cut and paste molecular process.
Formally, a splicing system is defined by giving an initial
language $I$ (initial set of DNA molecules)
and a set of special words or rules $R$ (enzymes).
The set $I$ is then transformed
by repeated applications of the splicing operation.
Intensive studies on linear splicing
systems and variants
have been done
and the generating power of these=20
systems has been compared with
classical models in formal language theory.
Our results
deal with finite linear splicing systems, i.e.,
with both $I,R$ finite sets.
Looking for a characterization of the
proper subclass of regular languages which are
generated by these systems,
we
consider
the still
open problem of deciding whether or not a
regular language $L \subseteq A^*$
belongs to this class of languages.
Unlike
the linear case,
relatively few works on
circular splicing systems and their languages
have been published.
A main result about the power of circular=20
splicing systems is due to Pixton who
proved that a circular regular language and
a finite set of rules
generate a regular language if the set of rules
satisfies some additional hypotheses.
We have focused our interest on
what
kind of regular
circular languages are generated by circular splicing
with both finite $I$ and $R$ and
we give results for unary languages.
We have also investigated
the computational power of these systems
and issues of algorithmic and descriptional
complexity.

%%% in case of several authors:
{\bf  Presented by Clelia De Felice}
%%%


\end{document}
_____________________________________________

\centerline{\large \bf Repetitiveness and extendability in finite
sequences}

%\centerline{\large \bf Title to be Continued Here if Too Long}

\bigskip

\centerline{Arturo Carpi}
\centerline{\it Dipartimento di Matematica e Informatica, Universit\`a
di Perugia, Italy}
\centerline{e-mail {\tt carpi@dipmat.unipg.it}}

%%% in case of several authors:
\smallskip
\centerline{Aldo de Luca}
\centerline{\it Dipartimento di Matematica, Universit\`a di Roma ``La
Sapienza'', Italy}
\centerline{e-mail {\tt deluca@mat.uniroma1.it}}
%%%

\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\par
%   Text of the abstract
We survey some recent developments of the combinatorial theory of
finite sequences of symbols (\emph{words}) on a finite set
(\emph{alphabet}) based on some structural properties of them, namely
\emph{extendability} and \emph{repetitiveness} of its factors (or
subwords) (cf.\ Carpi, de Luca, \emph{Theoret.\ Comput.\ Sci.}\
\textbf{259} (2001) 145--182).  More precisely, with each word $w$ we
associate two \emph{characteristic parameters}: the length $K_w$ of
the shortest unrepeated suffix of $w$ and the minimal natural number
$R_w$ such that $w$ has no (right) special factor of length $R_w$ (a
factor $v$ of $w$ is (right) \emph{special} if there exists two
distinct letters $x$ and $y$ such that $vx$ and $vy$ are still factors
of $w$).  Characteristic parameters give much information on the
structure of a word.  For instance, the maximal length of a repeated
factor of $w$ is given by $G_w=3D\max\{R_w, K_w\}-1$.  Some `uniqueness'
theorems for a word based on the knowledge of suitable sets of its
subwords have been proved.  In particular, a finite word $w$ is
uniquely determined by the set of its factors up to length $n=3DG_w+2$
and this value is optimal.  This result, which can be suitably
extended to more general combinatorial structures, is of interest for
`sequence assembly' which is a fundamental problem in molecular
Biology.  Some natural extensions of the notion of finite
\emph{periodic word} based on the characteristic parameters have been
considered in (Carpi, de Luca, \emph{Acta Inform.}\ \textbf{37} (2001)
597--618).  In particular, we obtained a generalization of the basic
periodicity theorem of Fine and Wilf.  Recently, we have studied how
the characteristic parameters, as well as some other related
quantities, are distributed among the words of each length.  Several
relations and results have been found concerning the functions
$D_{R}(i,n)$, $D_{K}(i,n)$, and $D_{G}(i,n)$ counting the number of
words $w$ of length $n$ such that, respectively, $R_{w}$, $K_{w}$, and
$G_{w}$ is equal to $i$.  For instance, on a $d$-letter alphabet,
$D_{R}(i,n+1)=3DD_{R}(i,n)+(d-1)D_{G}(i-1,n)$.  We found an explicit
formula for the number $D_{G}^*(i,n)$ of words of length $n$ having a
repeated factor of length $i\geq n/2$.  This formula gives an upper
bound for $D_{G}^*(i,n)$ in the general case.  Further results concern
\emph{uniform words}.  A word $w$ is called uniform if for any two
words $u$ and $v$ of the same length, the numbers of occurrences of
$u$ and $v$ in $w$ differ at most by 1.  Some characterizations of
uniform words are given.  We prove that on any finite alphabet there
exist uniform words of any length and an efficient algorithm allowing
one to construct for any $n$ a uniform word of length $n$ is given.

\medskip

%%% in case of several authors:
{\bf  Presented by Aldo de Luca}
%%%

\end{document}
___________________________________________________
\documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty} \textwidth=3D12.8cm \textheight=3D21.7cm
\hoffset=3D-0.3in \voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt
%------------------------------------------------------------
\begin{document}
\baselineskip=3D15pt

\centerline{\large \bf A Generalization of a Combinatorial Theorem
of Hall}

\centerline{\large \bf and an application to Erd\"os-Ginburg-Ziv
Theorem}

\bigskip

\centerline{Alberto Del Lungo} \centerline{\it Dipartimento di
Matematica, Universit\`a di Siena, Siena, Italy}
\centerline{e-mail {\tt dellungo@unisi.it}}

\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\par

Suppose $a_1,\ldots,a_n$ is a list of all the elements in a finite
abelian group $G$ of order $n$, and suppose a multiset
$C=3D\{c_1,\ldots, c_n\}$ of $n$ elements of $G$ is given.  A
multiset is like a set, except its elements need not be all
distinct. Let us now consider the following numerical matching
problem on $G$: is there a permutation $\pi_1,\ldots,\pi_n$ of
$a_1,\ldots,a_n$ such that
\begin{equation}
a_i + \pi_i =3D c'_i ,\quad  \mbox{for} \quad i=3D1,\ldots , n,
\label{dellungo1}
\end{equation}
where $c'_1,c'_2, \ldots, c'_n$ is a permutation of $c_1,\ldots,
c_n$ ?

Since $\sum_{i=3D1}^{n} a_i $, $\sum_{i=3D1}^{n} \pi_i $ would then
both be the sum of all elements of $G$, it is obviously necessary
that $\sum_{i=3D1}^{n} c_i =3D0$. Hall's theorem states that this
condition is also sufficient. More precisely,

\noindent {\bf Theorem (M. Hall).} If $G$ is a finite abelian
group of order $n$ with elements $\{a_1,\ldots, a_n\}$, and
$c_1,\ldots,c_n$ are $n$ (not necessarily distinct) elements of
$G$, then there exists a permutation $\pi=3D(\pi_1,\ldots,\pi_n)$ of
$\{a_1,\ldots, a_n\}$ such that:
$$
a_i + \pi_i =3D c'_i, \quad \mbox{for}\quad i=3D1,\ldots,n,
$$
where $c'_1,\ldots,c'_n$ is a permutation of $c_1,\ldots,c_n$ if
and only if
$
\sum_{i=3D1}^{n} c_i =3D0.
$

Marshall Hall Jr. proved this combinatorial theorem on the abelian
groups in 1952. The result was rediscovered by Salzborn and
Szekeres in 1979. Their proof is different from Hall's but of the
same ``level'' and ``difficulty''. The proof of Theorem given by
Hall, provides an algorithm which finds a permutation
$\pi_1,\ldots,\pi_n$ of $a_1,\ldots,a_n$ satisfying
condition~(\ref{dellungo1}) in time O$(n^2)$. Quite surprisingly,
the same numerical matching problem on ${\bf N}_0$ is NP-complete.

The main result of this paper is the following generalization of
Hall's theorem.

\noindent {\bf Theorem 1.} If $G$ is a finite abelian group of
order $n$ with elements $\{a_1,\ldots, a_n\}$, and
$c_1,\ldots,c_{kn}$ are $k n$ (not necessarily distinct) elements
of $G$, where $k$ is a positive integer number, then there exist
$k$ permutations
$\pi^{(1)}=3D(\pi^{(1)}_1,\ldots,\pi^{(1)}_n),\ldots ,
 \pi^{(k)}=3D(\pi^{(k)}_1,\ldots,\pi^{(k)}_n)$
of $\{a_1,\ldots, a_n\}$ such that:
\begin{equation}
a_i+\pi^{(h)}_i =3D  c^{(h)}_i \quad \mbox{for} \quad i=3D1,\ldots ,
n,\quad h=3D1,\ldots , k, \label{dellungo2}
\end{equation}
where $c^{(1)}_1,\ldots, c^{(1)}_n, \ldots, c^{(k)}_1,\ldots,
c^{(k)}_n$ is a permutation of the elements of $c_1,\ldots,c_{k
n}$ if and only if
$
\sum_{i=3D1}^{k\: n} c_i =3D0.
$

The theorem can be proved by using Erd\"os-Ginburg-Ziv theorem.

\noindent {\bf Theorem (Erd\"os-Ginburg-Ziv).} Let $G$ be a finite
abelian group of order $n$. If $C$ is a multiset of $G$ having
$2n-1$ elements, then there is $K\subset C$ such that $|K|=3Dn$ and
$\sum_{c\in K} c =3D0$.

By Erd\"os-Ginburg-Ziv theorem, every  multiset $C$ of $G$ with $k
n$ elements which sums to 0 can be split into $k$ subsets of size
$n$ which also sum to 0. By this result and Hall's Theorem,
Theorem 1 follows. We propose an alternative and direct proof of
Theorem 1. This proof provides an efficient algorithm for
determining a solution of the numerical matching problem. This
means that we have an efficient algorithm for determining the $k$
permutations $\pi^{(1)},\ldots , \pi^{(k)}$ of $G$ satisfying
condition~(\ref{dellungo2}).

We wish to point out that this approach gives a new proof of
Erd\"os-Ginburg-Ziv theorem. From this new proof, there follows an
algorithm which finds a subset $K$ of a multiset
$C=3D\{c_1,\ldots,c_{2n-1}\}$ of $G$ such that $|K|=3Dn$ and
$\sum_{c\in K} c =3D0$. The complexity of  this algorithm is $O(n^2
)$ in the worst case. We have implemented and tested the
algorithm, and the results of our experiments shows that the
average time for finding $K$ is $O(n)$.

\end{document}
___________________________________________

\documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty} \textwidth=3D12.8cm \textheight=3D21.7cm
\hoffset=3D-0.3in \voffset=3D-0.6in
\parskip=3D6pt\lineskip=3D18pt
\begin{document}

\baselineskip=3D15pt

\centerline{\large \bf String rewriting and magnifiers in
semigroups}



\bigskip
\centerline{Marin GUTAN}

\centerline{\it Universit\'e Blaise Pascal (Clermont-Ferrand II),
France}

\centerline{e-mail {\tt marin.gutan@math.univ-bpclermont.fr}}


\bigskip

\par

An element $a$ of a semigroup $S$ is called a (left) {\it
magnifier \/} if there exists a proper subset $M$ of $S$ such that
$aM =3D S$ (E. S. Ljapin). If there is a minimal subset $M$ with
this property which is a right ideal of $S$, then the magnifier
$a$ is called {\it very good}. If such a minimal subset is a
subsemigroup of $S$, then $a$ is called {\it good} (F.
Migliorini). Otherwise, it is called {\it  bad}. It is well known
that if a semigroup $S$ has a very good magnifier, then all
magnifiers in $S$ are very good. A long-standing open problem was
whether there exist semigroups having both good and bad
magnifiers. This problem has been recently solved by M. Gutan and
A. Kisielewicz. In this paper we show how to use string rewriting
systems for other problems raised up by F. Catino and F.
Migliorini (Semigroup Forum, 1992).

\bigskip
\end{document}
__________________________________


\documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty}
\textwidth =3D12.8cm
\textheight=3D21.7cm
\hoffset=3D-0.3in
\voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt
%------------------------------------------------------------
\begin{document}
\baselineskip=3D15pt

\centerline{\large \bf An Application of Combinatorics on Words}

\centerline{\large \bf to RNA Secondary Structure Design}

\bigskip

\centerline{Christine E. Heitsch}
\centerline{\it Department of Computer Science, University of
British Columbia, Canada}
\centerline{e-mail {\tt heitsch@cs.ubc.ca}}

\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\par

Given the basic mathematical nature of strings formed by
the concatenation of symbols from a finite alphabet, it is hardly
surprising that the field of combinatorics on words has connections
to many areas of mathematics and computer science.  Recently, however,
the techniques and results of string analysis have become increasingly
relevant to biology.  In particular, the vast amount of nucleotide
and protein sequence data has lead to the development of bioinformatics
and more generally computational / theoretical biology.

We present one problem from this fascinating area, the question of
RNA secondary structure design, and the combinatorial means of achieving
an algorithmic solution to an interesting special case.
Specifically, we use combinatorial analysis to transform an important
restriction of the computational problem of designing RNA base
sequences with a given minimal free energy secondary structure into
a coding theory question.  The difficulty lies in demonstrating that
a string of bases has no alternate secondary foldings with a lower
free energy than the desired configuration.

The primary RNA structure is a linear sequence of four nucleotides,
denoted A, U, C, and G, with the usual Watson-Crick base pairings,
plus other non-canonical matches.  Self-bonding forces the single RNA
strand into a complicated arrangement of stabilizing helical regions,
or ``stems,'' connected by single-stranded regions, or ``loops.''
Under a standard hypothesis, these planar structural arrangements can be
abstracted to their geometric ``skeleton''  and the description of
an RNA secondary structure reduced to a weighted plane tree on $n$ vertices.

We prove that it is possible to uniquely specify such a plane tree $T$ by
a balanced string over the alphabet  $A_{d}^{\pm} =3D \{1^{+}, 1^{-},
2^{+}, 2^{-}, \ldots, d^{+}, d^{-}\}$ where $d =3D \lceil \frac{m}{2}=
 \rceil$
and $m$ being the maximum number of edges of a vertex in $T$ is necessary
as well as sufficient.  We think of $k^{+}$ and $k^{-}$ as being
``complementary,''  and the pairs $k^{+} k^{-}$ and $k^{-} k^{+}$ as
representing the two different orientations of a helical RNA segment.

Furthermore, we extend this line of analysis to characterize the tree
structures which minimize and maximize the associated RNA loop energies
under our current model.  These bounds are used to analyze the potential
benefit of an alternate loop arrangement, and so to reduce the problem
of generating base pairs for the helical segments to a primarily coding
theory one.  Thus, these abstract combinatorial results have
important implications for the more practical concerns of nucleotide
molecular design which motivate our theoretical biology question.

\end{document}
_________________________________________________________________
\documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty}
\textwidth=3D12.8cm
\textheight=3D21.7cm
\hoffset=3D-0.3in
\voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt
%------------------------------------------------------------
\begin{document}
\baselineskip=3D15pt

\centerline{\large \bf Cones of Algebraic Power Series}

% \centerline{\large \bf Title to be Continued Here if Too Long}

\bigskip

\centerline{Werner Kuich}
\centerline{\it Technische Universit{\"a}t Wien, Austria}
\centerline{e-mail {\tt kuich@tuwien.ac.at}}

%%% in case of several
%authors:
%\smallskip
%\centerline{Author 2}
%\centerline{\it Institution Name, Country}
%\centerline{e-mail {\tt Author 2}}
%%%

\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
\par
A complete characterization of cones of algebraic power series in terms of=
=20
algebraic systems (context-free grammars) is given.
%   Text of the abstract

\bigskip

%%% in case of severalauthors:
%{\bf  Presented by ...}
%%%

\end{document}
________________________________________________

\documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty}
\textwidth=3D12.8cm
\textheight=3D21.7cm
\hoffset=3D-0.3in
\voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt
%------------------------------------------------------------

\begin{document}
\baselineskip=3D15pt

\centerline{\large \bf A geometric approach to semigroup theory}

\bigskip

\centerline{Jon McCammond}
\centerline{\it Texas A\&M University, USA}
\centerline{e-mail {\tt jon.mccammond@math.tamu.edu}}

%%% in case of several authors:
\smallskip
\centerline{John Rhodes}
\centerline{\it UC Berkeley, USA}
\centerline{e-mail {\tt rhodes@math.berkeley.edu}}
%%%

\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
\par
%   Text of the abstract
Geometric semigroup theory is the systematic
investigation of finitely-generated semigroups using the
topology and geometry of their associated automata.  In this
talk I will discuss how a number of easily-defined
expansions on finite automata lead to simplifications of the
corresponding semigroups.  In particular that every finite
semigroup can be finitely expanded so that the right Cayley
graph of the expansion closely resembles the right Cayley
graph of a free Burnside semigroup.

\bigskip

%%% in case of several authors:
{\bf  Presented by Jon McCammond}
%%%

\end{document}
______________________________________________________________
\documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty} \textwidth=3D12.8cm \textheight=3D21.7cm
\hoffset=3D-0.3in \voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt
%------------------------------------------------------------
\begin{document}
\baselineskip=3D15pt

\centerline{\large \bf A classification of two-generated finite groups}
\centerline{\large \bf in terms of sm-representability}

\bigskip

\centerline{Franco Migliorini, Simone Rinaldi} \centerline{\it Dipartimento=
 di
Matematica, Universit\`a di Siena, Siena, Italy}
\centerline{e-mail {\tt migliorini@unisi.it, rinaldi@unisi.it}}

\medskip

\par

Let ${\cal G}$ be a finite group and $\Omega $ a presentation of ${\cal G}$.=
=20
It is known (F. Migliorini, {\em Some topics and a classification in the
theory of sm-representation
of finite groups,}
Pu.M.A. 11 (2000) 521-532) that a {\em set-decomposition} is defined for
${\cal G}$ and=20
a representation of $\cal G$ exists by means of set-matrices ({\em
sm-representation}).
It is likewise known the central role of nilpotent groups as regards the
sm-representation of groups.
If $\cal G$ is a two-generated finite nilpotent group, the representability
index of $\cal G$ is equal=20
to the nilpotence class. After studying the case of non-nilpotent groups,
one gets a classification of
all two generated finite groups by considering their upper central series
and their type of
sm-representability. Nilpotent groups are classified by means of the
representability index, while for=20
non-nilpotent groups the main distinction is between absolutely
representable groups and the others.=20
By this classification, the main problem is to study the so called {\em
$(p,d,n)$-groups } with a=20
trivial center ($p,d,n\in \Bbb N$, $d$ odd). Several properties of
$(p,d,n)$-groups are determined.=20
Moreover symmetric and alternating groups, $S_n$ and $A_n$, are special
$(p,d,n)$-groups (except $A_3$).=20
Also dihedral groups $D_n$ provide interesting examples.

%%% in case of several authors:
{\bf  Presented by Franco Migliorini}
%%%


\end{document}

_____________________________


\documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty}
\textwidth =3D12.8cm
\textheight=3D21.7cm
\hoffset=3D-0.3in
\voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt
%------------------------------------------------------------
\begin{document}
\baselineskip=3D15pt

\centerline{\large \bf The Class
 of Finite Semigroups of Complexity at Most One}=20
\centerline{\large \bf Has=20
No Finite Basis of (Pseudo)Identities}



\bigskip

\centerline{Chrystopher L.\ Nehaniv}
\centerline{\it University of Hertfordshire,
United Kingdom}
\centerline{e-mail {\tt C.L.Nehaniv@herts.ac.uk}}

%%% in case of several
%authors:
%\smallskip
%\centerline{Author 2}
%\centerline{\it Institution Name,
%Country}
%\centerline{e-mail {\tt Author
%2}}
%%%

\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
\par
%   Text of the abstract
The Krohn-Rhodes (or group-) complexity of a finite semigroup $S$ is the
least number $n$ of group factors in any possible wreath product
decomposition of $S$: =20
$$S \twoheadleftarrow S' \hookrightarrow A_{n+1} \wr G_n \wr A_n \wr \cdots
\wr A_{i+1} \wr G_i \wr A_i \wr \cdots A_2 \wr G_1 \wr A_1,$$ =20
where $S$ is a homomorphic image of a subsemigroup $S'$ of the wreath=
 product,
and each $A_i$ is finite semigroup with only trivial subgroups and
each $G_i$ is a finite group.=20

The class ${\cal KR}(n)$ of finite semigroups=20
of complexity at most $n$ is a pseudovariety, i.e.\
a class closed under finitary products, homomorphic images, and=
 subsemigroups.
  =20
We construct for each positive integer $n$ a finite semigroup $S$ satisfying=
=20
\begin{enumerate}=20
\item $S$ cannot be generated by fewer than $n$ elements.
\item Every subsemigroup of $S$ generated by fewer than $n$ elements has
complexity less than $2$.
\item The Krohn-Rhodes complexity of $S$ is $2$.
\end{enumerate}

The proofs of the second and third properties use the Presentation Lemma,=
 and
the construction is based on an example due to John L.\ Rhodes.

It follows that there is no finite basis of identities for
${\cal KR}(1)$.  That is, there is no finite set of identities which
one can check to determine whether a semigroup is a member of ${\cal
KR}(1)$ or
not.  Similarly, there is no finite basis of pseudoidentities for ${\cal
KR}(1)$.
\bigskip


(This work benefitted from the discussions with J.\ Rhodes and M.\ Volkov.)
%%% in case of several authors: {\bf  Presented by ...}
%%%

\end{document}
__________________________________________
\documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty}
\textwidth=3D12.8cm
\textheight=3D21.7cm
\hoffset=3D-0.3in
\voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt
%------------------------------------------------------------
\begin{document}
\baselineskip=3D15pt

\centerline{\large \bf Optimal simulations between unary automata}

\bigskip

\centerline{Giovanni Pighizzini}
\centerline{\it Dipartimento di Scienze dell'Informazione\\
Universit\`a degli Studi di Milano, Italy}
\centerline{e-mail {\tt pighizzi@dsi.unimi.it}}


\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\par
We consider the problem of computing the costs (in terms of states)
of simulations between different kinds of finite automata recognizing
unary languages, namely, languages defined over a one letter input
alphabet.
We give a tight simulation of unary $n$-state two-way
nondeterministic automata by $O(e^{\sqrt{n \ln}})$-state one-way
deterministic automata.
Furthermore, we consider the simulation of two-way nondeterministic
automata by two-way deterministic automata. The problem of stating
the optimal cost of this simulation was proposed in 1978 by Sakoda
and Sipser. In particular, they conjecture that this cost is
exponential. We show that in the case of unary automata this
conjecture does not hold true. In fact, we get a subexponential
simulation.



\end{document}
_________________________________________________

\documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty}
\textwidth =3D12.8cm
\textheight=3D21.7cm
\hoffset=3D-0.3in
\voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt
%------------------------------------------------------------
\begin{document}
\baselineskip=3D15pt

\centerline{\large \bf Ordered Semigroups and Automata}

% \centerline{\large \bf Title to be Continued Here if Too Long}

\bigskip

\centerline{Jean-Eric Pin}
\centerline{\it LIAFA, CNRS and Universit\'e Paris VII}
\centerline{e-mail {\tt Jean-Eric.Pin@liafa.jussieu.fr}}


\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\par An ordered semigroup is a semigroup equipped with a partial order
compatible with the product.  In the 90's, I introduced the syntactic
ordered semigroup of a language and, extending Eilenberg's variety theorem,
I used this tool to obtain a one-to-one correspondence between varieties of
finite ordered semigroups and certain classes of recognizable languages,
called positive varieties.  This result had important consequences in the
study of languages of finite and infinite words and motivated a systematic
study of varieties of ordered semigroups.  In this lecture, I will review=
 the
results obtained during the last ten years and suggest some directions for
future research.


\bigskip


\end{document}
______________________________________________________
\documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty} \textwidth=3D12.8cm \textheight=3D21.7cm
\hoffset=3D-0.3in \voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt
%------------------------------------------------------------
\begin{document}
\baselineskip=3D15pt

\centerline{\large \bf Standard Sturmian Words}

%\centerline{\large \bf }

\bigskip

\centerline{Giuseppe Pirillo} \centerline{\it IMATI-CNR, Italy}
\centerline{e-mail {\tt pirillo@math.unifi.it}}

%%% in case of several authors:
%\smallskip
%\centerline{}
%\centerline{\it }
%\centerline{e-mail {\tt }}
%%%

\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\par
Sturmian words have been studied for a very long time (Bernoulli,
Christoffel, Morse and Hedlund, ...). They are infinite words that
have exactly $n+1$ factors of length $n$, for each $n\ge 0$. Thus
they are written on a binary alphabet. Standard Sturmian words
have numerous characteristic properties, in particular: a) A
Sturmian word is standard if and only if its prefixes are exactly
its left special factors. b) An infinite non ultimately periodic
word is standard Sturmian if and only if it can be obtained by
Rauzy rules. Here we present some recent characteristic properties
of Standard Sturmian words.


\bigskip

%%% in case of several authors:
%{\bf  Presented by ...}
%%%

\end{document}
_____________________________________________________
\documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty}
\textwidth=3D12.8cm
\textheight=3D21.7cm
\hoffset=3D-0.3in
\voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt
%------------------------------------------------------------
\begin{document}
\baselineskip=3D15pt

\centerline{\large \bf On Syntactic Semirings}

%\centerline{\large \bf Title to be Continued Here if Too Long}

\bigskip

\centerline{Libor Pol\'ak}
\centerline{\it Masaryk University Brno, Czech Republic}
\centerline{e-mail {\tt polak@math.muni.cz}}


\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
\par
%   Text of the abstract
Recently the author introduced the notion of the syntactic semiring of=20
a given language $L$ over a finite alphabet $A$.
Let $F(A^*)$ be the set of all non-empty finite sets of words over $A$.
Notice
that the algebra $(F(A^*),\cdot,\cup)$ is a free idempotent semiring
over $A$. Now $L$ defines a congruence $\sim_L$  of this semiring by
$$\{u_1,\dots,u_k\} \sim_L \{v_1,\dots, v_l\}
\mbox{\ if and only if }$$                  =20
$$(\ \forall\ p,q\in A^*\ )\ (\ pu_1q,...,pu_kq\in L
\iff pv_1q,...,pv_lq\in L\ )\enspace .$$  =20
The factor-structure is called the {\em syntactic semiring} of $L$.
It is finite if and only if the language $L$ is regular.
Also a theory of recognizability of languages by idempotent semirings
follows the classical one dealing with monoids.
In certain sense our notion is a modification of the Reutenauer syntactic
algebra for the case of the Boolean semiring.

Let us point out several applications of syntactic semirings in language
theory.

1. We can prove an Eilenberg-type theorem
giving a one-to-one correspondence between the so-called
conjunctive varieties of regular languages and pseudovarieties
of idempotent semirings.
At present we do not have such striking examples of properties of
languages characterizable by their syntactic semirings=20
as in the case of syntactic monoids (aperiodicity, piecewise=
 testability,...).

2. Syntactic semirings also help us in studying an ordered version of the
``power'' operator on classes of ordered monoids.=20
This leads to generalizations of results relating operators on classes
of regular languages and the power operator on pseudovarieties of monoids.

3. We can discuss inequalities $r(x_1,\dots,x_m) \subseteq L$
and equations $r(x_1,\dots,x_m)=3DL$,=20
where $L$ is a given regular language over a finite alphabet $A$
and $r$ is a given regular
expression over $A$ in variables $x_1,\dots,x_m$.
We show  that the search for maximal solutions can be translated
into the (finite) syntactic semiring of the language $L$.
In such a way we are able to decide the solvability and to find all
maximal solutions effectively.
In fact, the inequalities  $r(x_1,\dots,x_m) \subseteq L$ were considered
already by Conway. In our approach the number of candidates for=20
components of maximal solutions  =20
is exponentially smaller.=20
Moreover, we use transparent calculations in a finite structure whose
elements are represented by mappings.

The present research concerns the pointed idempotent semirings
(the point corresponds to the image of the language in its syntactic
semiring) and connections of the so-called Conway universal machine
with our structure.

\end{document}
_________________________________________________

\documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty}
\textwidth=3D12.8cm
\textheight=3D21.7cm
\hoffset=3D-0.3in
\voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt
%------------------------------------------------------------
\begin{document}
\baselineskip=3D15pt

\centerline{\large \bf Decipherability of codes and Kraft
inequality}

%\centerline{\large \bf Title to be Continued Here if Too Long}

\bigskip

\centerline{Antonio Restivo} \centerline{\it Universit\`a di
Palermo, Italy} \centerline{e-mail {\tt restivo@math.unipa.it}}

%%% in case of several authors:
%\smallskip
%\centerline{Author 2} \centerline{\it Institution Name,Country}
%\centerline{e-mail {\tt Author 2}}
%%%

\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
\par
%   Text of the abstract
Decipherability conditions for codes are investigated by using the
approach of Guzman, who introduced the notion of variety of codes
and established a connection between classes of codes and
varieties of monoids. The class of Uniquely Decipherable (UD)
codes is a special case of variety of codes, corresponding to the
variety of all monoids.

It is well known that the Kraft inequality is a necessary
condition for UD codes, but it is not sufficient in the sense that
there exist codes that are not UD and that satisfy the Kraft
inequality. The main result of the present paper states that,
given a variety ${\cal V}$ of codes, if all the elements of ${\cal
V}$ satisfy the Kraft inequality, then ${\cal V}$ is the variety
of UD codes. Thus, in terms of varieties, Kraft inequality
characterizes UD codes.
\bigskip

%%% in case of several authors:
%{\bf  Presented by ...}
%%%

\end{document}
__________________________________
documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty} \textwidth=3D12.8cm \textheight=3D21.7cm
\hoffset=3D-0.3in \voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt

\begin{document}
\baselineskip=3D15pt

\centerline{Proof of the decidability of group complexity $c$ for
finite semigroups and finite state automata}
\bigskip

\centerline{John Rhodes}
\centerline{Department of Mathematics\\
University of California\\Berkeley, California 94720--3840}
\centerline{rhodes@math.berkeley.edu}



\bigskip\par
Due to an unfortunate error in a standard paper in the field, an
error recently discovered by B.Steinberg and me, my old proof that
$c$ is decidable has been withdrawn from publication. My new proof
uses Ramsey Theory via the Finite Products Theorem, as well as the
Presentation Lemma and other elements of the old proof; these
replace previously-used incorrect techniques.

The new proof also relies heavily on Geometric Semigroup Theory
devised by J.McCammond and me, as well as the Presentation Lemma
in flow version using the finite lattice of flows. The q-theory
B.Steinberg and I developed is additionally helpful in simplifying
the proof conceptually.
\end{document}

________________________________________
\documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty}
\textwidth=3D12.8cm
\textheight=3D21.7cm
\hoffset=3D-0.3in
\voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt
%------------------------------------------------------------
\begin{document}
\baselineskip=3D15pt

\centerline{\large \bf Subsemigroups of the Bicyclic Monoid}


\bigskip
\centerline{Luis Descal\c{c}o}
\centerline{\it University of St Andrews, Scotland, U.K.}
\centerline{e-mail {\tt luisd@mcs.st-and.ac.uk}}

%%% in case of several authors:
\smallskip
\centerline{Nik Ru\v{s}kuc}
\centerline{\it University of St Andrews, Scotland, U.K.}
\centerline{e-mail {\tt nik@mcs.st-and.ac.uk}}

%%%


\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
\par
%   Text of the abstract



The subsemigroups of the bicyclic monoid
$B=3D\langle b,c\:|\: bc=3D1\rangle$ can be classified into three types:
\begin{itemize}
\item
diagonal: containing just elements of the form $c^ib^i$;
\item
one-sided: containing elements of one of the forms $c^ib^j$ ($i>j$)
or $c^ib^j$ ($i<j$) but not both;
\item
two-sided: containing elements of both the above forms.
\end{itemize}
The diagonal type is degenerate (and trivial): every subset
of $\{ c^ib^i\::\: i=3D0,1,2,3,\ldots\}$
is a subsemigroup.
Every other subsemigroup consists, roughly speaking, of a `small'
irregular part and the remainder which is highly regular.
More precisely, it can be
described by a number of parameters.
These descriptions are strong enough to enable
us to prove the following:
\begin{itemize}
\item
A subsemigroup of $B$ is not finitely generated if and only if it is
infinite diagonal or one-sided with a non-empty intersection with infinitely
many
sets $H_i=3D\{ c^ib^j\::\: j=3D0,1,2,\ldots\}$ ($i=3D0,1,2,\ldots$)
and infinitely many sets $V_j=3D\{c^ib^j\::\: i=3D0,1,2,\ldots\}$
($j=3D0,1,2,\ldots$).
\item
Every finitely generated subsemigroup of $B$ is finitely presented.
\item
Every finitely generated subsemigroup of $B$ is
(left, right and bi-) automatic.
\item
A subsemigroup of $B$ is residually finite if and only if it is
not two-sided.
\end{itemize}

If a subsemigroup of $B$ is given by a (finite) set of generators,
then one can algorithmically decide of which type it is,
and effectively compute the parameters characterising it.
These algorithms have been implemented in {\sf GAP}.


\bigskip

%%% in case of several authors:
{\bf  Presented by Nik Ru\v{s}kuc}
%%%
________________________________________

\documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\pagestyle{empty}
\textwidth =3D12.8cm
\textheight=3D21.7cm
\hoffset=3D-0.3in
\voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt



\begin{document}
\baselineskip=3D15pt

\centerline{\large\bf Categorical algebras of automata}

%\centerline{\large \bf Title to be Continued Here if Too Long}
%

\bigskip

\centerline{N. Sabadini} \centerline{\it University of Insubria, Italy}
\centerline{e-mail {\tt nicoletta.sabadini@uninsubria.it}}

\smallskip\centerline{R.F.C. Walters} \centerline{\it University of
Insubria, Italy} \centerline{e-mail {\tt robert.walters@uninsubria.it}}

\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%

We describe two categorical algebras of automata designed for the
compositional description, and verification of distributed systems, and
describe two results relating to these algebras.

We define a \emph{category with feedback }to be a symmetric monoidal
category
$\mathbf{A}$ with, for each triple $A,B,U$ of objects, an operation
$feedback_{U}:\mathbf{A}(A\otimes U,B\otimes U)\rightarrow\mathbf{A}(A,B)$
satisfying a subset of the Joyal-Street-Verity axioms of $trace$. The main
difference is that $feedback(twist_{A,A})$ is not necessarily $1_{A}$, but
rather is a \emph{delay} element. Then we show that a variety of interesting
categories of automata (Mealy automata, Elgot automata, NFA, etc) arise as
the
free categories with feedback on different monoidal categories. The free
category with feedback construction is a generalization of that of the free
cancellative monoid on a commutative monoid (applying to monoidal categories
rather than monoids). Killing the delay elements in a category with feedback
yields a traced monoidal category, to which the Joyal-Street-Verity $Int$
construction may be applied resulting in a compact closed category. The
combined construction, from symmetric monoidal to compact closed is a
generalization of the free abelian group on a commutative monoid.

The second concrete algebra has as elements \emph{cospans of spans of
graphs,}
though in this lecture we concentrate on the category of \emph{spans of
graphs}. The elements of this algebra may be thought of as automata; the
main
operations are \emph{parallel }and \emph{series }(communicating parallel) of
automata. We introduce a notion of simulation of automata (closely related
to
branching bisimulation), and a \emph{bisimulation monoid }whose elements are
bismulation classes of automata. We demonstrate that there are various
interesting finite submonoids of this monoid, giving a partial explanation
for
the partial success of compositional model checking algorithms. In
particular
we show that in the classical dining philosopher problem if $P$ is a
philosopher and $F$ is a fork then $(P.F)^{3}=3D(P.F)^{2}.$

\textbf{Presented by N. Sabadini}
\end{document}
____________________________________________

\documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty}
\textwidth=3D12.8cm
\textheight=3D21.7cm
\hoffset=3D-0.3in
\voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt
%------------------------------------------------------------
\begin{document}
\baselineskip=3D15pt

\centerline{\large \bf On the universal automaton of a language}

% \centerline{\large \bf Title to be Continued Here if Too Long}

\bigskip

\centerline{Sylvain Lombardy}
\centerline{\it ENST, France}
\centerline{e-mail {\tt lombardy@enst.fr}}

\smallskip
\centerline{Jacques Sakarovitch}
\centerline{\it ENST / CNRS, France}
\centerline{e-mail {\tt sakarovitch@enst.fr}}

\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
\par
%   Text of the abstract

Since almost 40 years, the theory of rational languages --- or at least=20
a part of it --- has developped along an algebraic line, so that it is=20
now naturally associated  with semigroup theory.=20
The bridge being the definition of the \emph{minimal automaton} of a=20
language and its transition monoid called the \emph{syntactic monoid}=20
of the language.

In 1971, J. H. Conway published a marvellous small book on the=20
subject of formal languages: \emph{Regular algebra and finite machines}=20
where he introduced a number of new and profound ideas.
In particular, he solved the problem of deciding whether a given=20
rational language~$L$ belongs to the rational closure of a given finite=20
set of rational languages by means of the construction of what he=20
called the \emph{factor matrix} of~$L$.
This matrix is easily turned into a finite automaton, canonically=20
attached to~$L$ and which we propose to call the \emph{universal automaton}=
=20
of~$L$.

First, the universal automaton of~$L$ contains a morphic image  of=20
any automaton (even not deterministic) that recognizes~$L$ and is the=20
smallest automaton with that property.
The idea underlying further investigations is that it is possible to=20
characterize certain properties of a language~$L$ by means of its=20
universal automaton, in the same way as some other properties of~$L$=20
can be characterized by means of its minimal automaton or its=20
syntactic monoid.

So far, this approach has been successful for the study of=20
\emph{reversible languages}.
We have shown that the universal automaton of such a language=20
contains an equivalent subautomaton with minimal loop complexity=20
(which thus solves the \emph{star heigt problem} for this class of=20
languages) and which is quasi-reversible.
Such properties do not hold for the minimal automaton of a reversible=20
language.

\bigskip

%%% in case of several authors:
{\bf  Presented by Jacques Sakarovitch}
%%%

\end{document}
______________________________________________

\documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty} \textwidth=3D12.8cm \textheight=3D21.7cm
\hoffset=3D-0.3in \voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt
%------------------------------------------------------------
\begin{document}
\baselineskip=3D15pt

\centerline{\large \bf Residual finiteness of ascending HNN
extensions of free groups. }


\bigskip


%%% in case of several authors:
\smallskip
\centerline{Mark Sapir} \centerline{\it Vanderbilt University,
USA} \centerline{e-mail {\tt msapir@math.vanderbilt.edu}}

%%%


\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
\par
%   Text of the abstract



This is a joint talk with A. Borisov. We prove that any ascending
HNN extension of the free group of rank 2 is residually finite. We
also prove that a "generic" ascending HNN extension of any free
group is residually finite. The proof is based on the reduction of
the residual finiteness problem to a problem about periodic points
of polynomial maps on algebraic varieties.




\bigskip

%%% in case of several authors:
{\bf  Presented by Mark Sapir}
%%%

\end{document}
_____________________________________________
\documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty}
\textwidth=3D12.8cm
\textheight=3D21.7cm
\hoffset=3D-0.3in
\voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt
%------------------------------------------------------------
\begin{document}
\baselineskip=3D15pt

\centerline{\large \bf Rational subsets of the free group}

%\centerline{\large \bf Title to be Continued Here if Too Long}

\bigskip

\centerline{Pedro V. Silva}
\centerline{\it University of Porto, Portugal}
\centerline{e-mail {\tt pvsilva@fc.up.pt}}

\bigskip

\par
In a paper published in 1996, G\'eraud S\'enizergues proved a
conjecture proposed by Jacques Sakarovitch in 1979: every rational
subset of the free group must be either recognizable or disjunctive
(the corresponding syntactical congruence is the identity).=20
As a consequence, an algorithm to determine whether or not a rational
subset of the free group is recognizable was found. Taking this
problem as a departure point, we developed two alternative approaches
to S\'enizergues's that allow us to obtain variouys algorithmic
characterizations of recognizability as well as alternative proofs of=20
S\'enizergues's results, including the conjecture of Sakarovitch.

The first approach uses techniques inspired by the study of inverse
monoids and inverse automata and provides a wide variety of=
 characterizations.

The second approach is more universal and allows generalizations to
other classes of groups.

\end{document}
_____________________________________________


\documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty} \textwidth=3D12.8cm \textheight=3D21.7cm
\hoffset=3D-0.3in \voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt
%------------------------------------------------------------
\begin{document}
\baselineskip=3D15pt

\centerline{\large \bf The $q$-theory of finite semigroups}

%\centerline{\large \bf Title to be Continued Here if Too Long}

\bigskip

\centerline{John Rhodes} \centerline{\it University of California
at Berkeley, USA} \centerline{e-mail {\tt
rhodes@math.berkeley.edu}}

%%% in case of several authors:
\smallskip
\centerline{Benjamin Steinberg} \centerline{\it University of
Porto, Portugal} \centerline{e-mail {\tt bsteinbg@agc0.fc.up.pt}}

%%%

\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
\par
%   Text of the abstract

In this talk, we introduce the notion of a continuous operator on
the lattice of pseudovarieties and the global Malcev condition. We
then introduce two classes of set of relational morphisms:
continuously closed classes and pseudovarieties of relational
morphisms. We also introduce composition of such classes.

The operator $q$ is introduced which takes continuously closed
classes onto continuous operators and pseudovarieties of
relational morphisms onto those which satisfy the global Malcev
condition. Moreover, $q$ is simultaneously a monoid homomorphism
and the lower part of a Galois connection between complete
lattices.

All commonly studied pseudovariety operators fit into this scheme
work and are hence amenable to study via classes of relational
morphisms.

We speak about order properties of all lattices involved.  In the
satellite conference, we shall speak of the equational theory of
pseudovarieties of relational morphisms.

\bigskip

%%% in case of several authors:
{\bf  Presented by Benjamin Steinberg}
%%%

\end{document}
_________________________________________

\documentclass{article}
%%\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty}
\textwidth=3D12.8cm
\textheight=3D21.7cm
\hoffset=3D-0.3in
\voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt
%------------------------------------------------------------
\begin{document}
\baselineskip=3D15pt

\centerline{Weakly Iterated Block Products of Finite Monoids}

%\centerline{\large \bf Title to be Continued Here if Too Long}

\bigskip

\centerline{Howard Straubing}
\centerline{Computer Science Department, Boston College}
\centerline{Chestnut Hill, Massachusetts, USA}
\centerline{straubin@cs.bc.edu}

%%% in case of several authors:add other names and addresses etc} %%%
\bigskip
\centerline{Denis Th\'erien}
\centerline{School of Computer Science, McGill University}
\centerline{Montr\'eal, Qu\'ebec, Canada}
\centerline{denis@opus.cs.mcgill.ca}

\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\par
%   Text of the abstract
In the work of Rhodes and Tilson, and, implicitly, in a much older paper
of Krohn, Mateosian and Rhodes,  we find the following bilateral
version of the Krohn-Rhodes theorem: Every finite monoid $M$  divides an=20
iterated bilateral semidirect product
$$(M_n**.. (M_3**(M_2**M_1)...)$$
where each $M_i$ is either a semilattice or a simple group that divides $M$.=
 =20
In particular, if $M$ is aperiodic, then $M$ divides an iterated product of=
=20
semilattices.  While bilateral products are somewhat unwieldy to work with,=
=20
they result in decompositions with simpler factors than are possible with=20
unilateral products, making them especially suitable for some applications
involving regular languages.
=20
In the present paper we consider what happens when we bracket the iterated=
=20
bilateral semidirect product in the opposite direction.  We find that the
monoids that divide an iterated bilateral semidirect product
$$((...(M_1**M_2)**M_3)**... **M_n)$$
of semilattices are precisely the members
of the pseudovariety {\bf DA}, and those that divide an iterated product of
groups and semilattices are precisely the members of {\bf DA*G}.
This constitutes a kind of ``inside-out'' Krohn-Rhodes theorem. We also
give an
application of our decomposition result: A new, transparent proof of
a theorem of the authors on the definability of regular languages by
sentences with two variables.
                  =20
\medskip

%%% in case of several authors:
{\bf  Presented by Howard Straubing}
%%%

\end{document}

________________________________________
\documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty}
\textwidth=3D12.8cm
\textheight=3D21.7cm
\hoffset=3D-0.3in
\voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt
%------------------------------------------------------------
\begin{document}
\baselineskip=3D15pt

\centerline{\large \bf Join-irreducible classes of semigroups}

\bigskip

\centerline{A. Vernitski}
\centerline{\it Middlesex University, UK}
\centerline{e-mail {\tt a.vernitski@mdx.ac.uk}}

\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
\par
In a lattice, join-irreducible elements have a special meaning, because they
are intuitively perceived as primitive ``building blocks'', with which we
can build ``composite'' elements of the lattice. A \textit{pseudovariety} is
a class of finite algebras of one type closed under the formation of direct
products of two algebras, subalgebras and factor-algebras. By
\textit{pseudoquasivariety} I shall mean a class of (not necessarily finite)
algebras of one type closed under the formation of direct products of two
algebras and subalgebras. The lattice of pseudovarieties is a subposet, but
not a sublattice of the lattice of pseudoquasivarieties.

Applying techniques based on those from [1], for several well-known
pseudovarieties of semigroups, I have proved that they are join-irreducible
as pseudoquasivarieties. As to their join-irreducibility as pseudovarieties,
the answer is sometimes positive, sometimes negative, sometimes unknown. For
example, the classes J [L, R, A] of finite J-[L-,R-,H-]trivial semigroups
are all join-irreducible as pseudoquasivarieties. It is known that J is not
join-irreducible as a pseudovariety, yet A is join-irreducible as a
pseudovariety. Now I am trying to prove that every pseudovariety containing
J is join-irreducible as a pseudoquasivariety.

Also, for some pseudoquasivarieties of (not necessarily only finite)
semigroups I have proved that they are join-irreducible. For example, such
are each class consisting of semigroups whose cardinality is less than a
given infinite cardinal, and, for each pseudoquasivariety of groups G, the
class of all [finite] semigroups whose subgroups belong to G.

\textbf{Literature}

[1] Margolis, S., M. Sapir, P. Weil, \textit{Irreducibility of certain
pseudovarieties}, Commun. Algebra 26 (1998), 779-792.

\end{document}


________________________________________
\documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty}
\textwidth
=3D12.8cm
\textheight=3D21.7cm
\hoffset=3D-0.3in
\voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt
%------------------------------------------------------------
\begin{document}
\baselineskip=3D15pt

\centerline{\large \bf Some properies of non-self embedding
grammars}



\bigskip

\centerline{Marcella Anselmo }
 \centerline{\it  Dipartimento  di Informatica ed Applicazioni, Universit\`a
di Salerno, Italy}
  \centerline{e-mail {\tt anselmo@dia.unisa.it}}

%%% in case of several

\smallskip
\centerline{Dora Giammarresi}
  \centerline{\it Dipartimento di Matematica, Universit\`a di Roma ``Tor
Vergata", Italy}
\centerline{e-mail {\tt giammarr@mat.uniroma2.it}}

\smallskip
\centerline{Stefano Varricchio}
  \centerline{\it Dipartimento di Matematica, Universit\`a di Roma ``Tor
Vergata", Italy}
\centerline{e-mail {\tt varricch@mat.uniroma2.it}}
%%%

\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
\par

A context-free grammar is {\em non-self embedding} (NSE) if for
any variable $A$, there are no  derivations of type
$A\stackrel{*}{\Longrightarrow} \alpha A\beta$ with both $\alpha,
\beta$ non-empty. A well known result of Chomsky states that NSE
grammars generate only regular languages.

We   investigate  the  consequences of the   NSE property on the
grammar structure. We show that a NSE grammar can be expressed in
terms of regular grammars. More precisely, we introduce an
operation between grammars, called $\oplus$-{\em composition},
that corresponds to the  substitution operation between languages.
Then we characterize the NSE grammars as those grammars that can
be obtained by a finite number of $\oplus$-compositions of regular
grammars. As immediate consequence one obtains the
 Chomsky result, since regular languages are closed under regular
substitutions.



 We then investigate what the NSE property yields on
the push-down automata (PDA). We obtain that a PDA, obtained by
the canonical construction from a NSE grammar, has stack's size
bounded by some constant. Moreover, we prove that if a PDA has
stack's size bounded by a constant, then the corresponding
equivalent context-free grammar is NSE.


We consider regular definitions, that are a formalism extending
regular expressions, used in compiling, for example by $Lex$ . We
show that the representation by NSE grammars and the one by
regular definitions are polynomially equivalent. We also discuss
the realization of rational operations on languages using NSE
grammars and  we observe that one has an advantage with respect to
finite automata in many situations: for instance in the
representation of the square of a language, or, more generally, in
the representation of regular expressions containing different
instances of the same language. Moreover, we remark that rational
operations have a very easy representation in terms of
$\oplus$-composition of NSE grammars.

  Finally, we give an algorithm that tests  whether a context-free grammar
is
NSE or not. The running time is polynomial  in the size of the
grammar.


\bigskip

 {\bf  Presented by Stefano Varricchio}
%%%

\end{document}
________________________________________
\documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty}
\textwidth=3D12.8cm
\textheight=3D21.7cm
\hoffset=3D-0.3in
\voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt
%------------------------------------------------------------
\begin{document}
\baselineskip=3D15pt
Di seguito trover=E0 gli abstract della sezione speciale "Semigroups,
Automata and Formal Languages", mi faccia sapere se nella compilazione
degli abstract nascono problemi.
Pu=F2 essere che abbia fatto qualche pasticcio nel copiarli.
Il programma =E8 invece inviato come file in allegato
Cordiali saluti e grazie=20

Alessandra Cherubini

\centerline{\large \bf The finite basis problem}

\centerline{\large \bf for semigroups of triangular matrices}

\bigskip


\centerline{I. A. Goldberg}
\centerline{\it Ural State University, Russia}
\centerline{e-mail {\tt Goldberg@skbkontur.ru}}

\smallskip

\centerline{M. V. Volkov}
\centerline{\it Ural State University, Russia}
\centerline{e-mail {\tt Mikhail.Volkov@usu.ru}}

\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
\par
Let $K$ be a finite field, $T_n(K)$ the semigroup of all triangular
$n\times n$-matrices over $K$. The question of whether the identities
of the semigroup $T_n(K)$ for $n>1$ admit a finite basis has been
several times mentioned in the literature.

A finite semigroup $S$ is said to be \emph{inherently non-finitely
based} if no finitely based locally finite variety contains $S$.
We prove that the semigroup $T_n(K)$ is inherently non-finitely based
if and only if $|K|>2$ and $n>3$.

\bigskip

%%% in case of several authors:
{\bf  Presented by M. V. Volkov}
%%%

\end{document}
___________________________________________________
\documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty}
\textwidth=3D12.8cm
\textheight=3D21.7cm
\hoffset=3D-0.3in
\voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt
%------------------------------------------------------------
\begin{document}
\baselineskip=3D15pt

\centerline{\large \bf Ordered Semigroups and Automata 2}

\bigskip

\centerline{Pascal Weil}
\centerline{\it LaBRI, CNRS and Universit\'e Bordeaux-1, France}
\centerline{e-mail: {\tt pascal.weil@labri.fr}}


\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\par

This talk is a continuation of the talk proposed by Jean-Eric Pin on=20
ordered semigroups (products of such semigroups, pseudovarieties),=20
ordered automata, and their applications to language theory,=20
especially to the study of concatenation hierarchies.

\bigskip

\end{document}
_____________________________________________________


\documentclass{article}
\usepackage{amsthm,amsmath,amssymb,latexsym}
\pagestyle{empty}
\textwidth=3D12.8cm
\textheight=3D21.7cm
\hoffset=3D-0.3in
\voffset=3D-0.6in
\parskip=3D6pt
\lineskip=3D18pt
\begin{document}
\baselineskip=3D15pt

\centerline{\large \bf=20
Embedding theorems for groups presented via partial automorphisms}
\bigskip

\centerline{Akihiro Yamamura}
\centerline{\it Communications Research Laboratory, Japan}
\centerline{e-mail {\tt aki@crl.go.jp}}


\bigskip
\par

We examine a certain embedding=20
problem for groups=20
that have a presentation described=20
by partial automorphisms.
The embedding problem is formalized
as follows.
Let $G$, $H$ be groups.
Each generator $h$ of $H$=20
corresponds to an isomorphism
$\phi_h$ of a subgroup $A_h$ of $G$=20
onto a subgroup
$B_h$ of $G$.
Let $K$ be the group=20
presented by
${\rm Gp}(G,\; H\; |\; ax=20
=3D x(a\phi_x)\; {\rm for}\;
\forall a \in A_x,\; \forall x \in X)$,
where $H$ is generated by $X$.
Is the natural homomorphism=20
$\xi_G$ of $G$ into $K$
an isomorphism?
Is the natural homomorphism=20
$\xi_H$ of $H$ into $K$
an isomorphism?
If the answer is ``no'',=20
then under what condition are=20
$\xi_G$ and $\xi_H$ isomorphisms?
Can we generalize Britton's lemma=20
and the normal form theorem
for HNN extensions?
This problem is closely=20
related to algebraic=20
systems of partial automorphisms,
formalized by the concept of inverse semigroups.
We clarify the close relationship
between the embeddability and the algebraic
structure of the inverse semigroup, give an
answer to the question using van Kampen diagrams.

\bigskip


\end{document}

