\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$ ($i1$ 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}