Search results for "Combinatorics"
showing 10 items of 1770 documents
Epichristoffel Words and Minimization of Moore Automata
2014
This paper is focused on the connection between the combinatorics of words and minimization of automata. The three main ingredients are the epichristoffel words, Moore automata and a variant of Hopcroft's algorithm for their minimization. Epichristoffel words defined in [14] generalize some properties of circular sturmian words. Here we prove a factorization property and the existence of the reduction tree, that uniquely identifies the structure of the word. Furthermore, in the paper we investigate the problem of the minimization of Moore automata by defining a variant of Hopcroft's minimization algorithm. The use of this variant makes simpler the computation of the running time and consequ…
On the Shuffle of Star-Free Languages
2012
Motivated by the general problem to characterize families of languages closed under shuffle, we investigate some conditions under which the shuffle of two star-free languages is star-free. Some of the special cases here approached give rise to new problems in combinatorics on words.
On the classification of algebraic function fields of class number three
2012
AbstractLet F be an algebraic function field of one variable having a finite field Fq with q>2 elements as its field of constants. We determine all such fields for which the class number is three. More precisely, we show that, up to Fq-isomorphism, there are only 8 of such function fields. For q=2 the problem has been solved under the additional hypothesis that the function field is quadratic.
A smallest irregular oriented graph containing a given diregular one
2004
AbstractA digraph is called irregular if its vertices have mutually distinct ordered pairs of semi-degrees. Let D be any diregular oriented graph (without loops or 2-dicycles). A smallest irregular oriented graph F, F=F(D), is constructed such that F includes D as an induced subdigraph, the smallest digraph being one with smallest possible order and with smallest possible size. If the digraph D is arcless then V(D) is an independent set of F(D) comprising almost all vertices of F(D) as |V(D)|→∞. The number of irregular oriented graphs is proved to be superexponential in their order. We could not show that almost all oriented graphs are/are not irregular.
On the loopless generation of binary tree sequences
1998
Weight sequences were introduced by Pallo in 1986 for coding binary trees and he presented a constant amortized time algorithm for their generation in lexicographic order. A year later, Roelants van Baronaigien and Ruskey developed a recursive constant amortized time algorithm for generating Gray code for binary trees in Pallo's representation. It is common practice to find a loopless generating algorithm for a combinatorial object when enunciating a Gray code for this object. In this paper we regard weight sequences as variations and apply a Williamson algorithm in order to obtain a loopless generating algorithm for the Roelants van Baronaigien and Ruskey's Gray code for weight sequences.
An Efficient Algorithm for the Generation of Z-Convex Polyominoes
2014
We present a characterization of Z-convex polyominoes in terms of pairs of suitable integer vectors. This lets us design an algorithm which generates all Z-convex polyominoes of size n in constant amortized time.
On 2-(n^2,2n,2n-1) designs with three intersection numbers
2007
The simple incidence structure $${\mathcal{D}(\mathcal{A},2)}$$ , formed by the points and the unordered pairs of distinct parallel lines of a finite affine plane $${\mathcal{A}=(\mathcal{P}, \mathcal{L})}$$ of order n > 4, is a 2 --- (n 2,2n,2n---1) design with intersection numbers 0,4,n. In this paper, we show that the converse is true, when n ? 5 is an odd integer.
On Sturmian Graphs
2007
AbstractIn this paper we define Sturmian graphs and we prove that all of them have a certain “counting” property. We show deep connections between this counting property and two conjectures, by Moser and by Zaremba, on the continued fraction expansion of real numbers. These graphs turn out to be the underlying graphs of compact directed acyclic word graphs of central Sturmian words. In order to prove this result, we give a characterization of the maximal repeats of central Sturmian words. We show also that, in analogy with the case of Sturmian words, these graphs converge to infinite ones.
Potential approach in marginalizing Gibbs models
1999
Abstract Given an undirected graph G or hypergraph potential H model for a given set of variables V , we introduce two marginalization operators for obtaining the undirected graph G A or hypergraph H A associated with a given subset A ⊂ V such that the marginal distribution of A factorizes according to G A or H A , respectively. Finally, we illustrate the method by its application to some practical examples. With them we show that potential approach allow defining a finer factorization or performing a more precise conditional independence analysis than undirected graph models. Finally, we explain connections with related works.
Grundy coloring for power graphs
2003
International audience