Narrow Results

Motzkin paths with air pockets (MAP) of the first kind are defined as a generalization of Dyck paths with air pockets. They are lattice paths in ${\mathbb{N}}^2$ starting at the origin made of steps $U=(1,1)$, $D_i=(1,-i)$, $i\ge 1$, and $H=(1,0)$, where two down-steps cannot be consecutive. We enumerate MAP and their prefixes avoiding peaks (respectively, valleys, respectively, double rise) according to the length, the type of the last step, and the height of its end-point. We express our results using Riordan arrays. Finally, we provide constructive bijections between these paths and restricted Dyck and Motzkin paths.

Remmel and Williamson recently defined a class of directed graphs, called filtered digraphs, and described a natural class of bijections between oriented spanning forests of these digraphs and associated classes of functions [12]. Filtered digraphs include many specialized graphs such as complete k-partite graphs. The Remmel-Williamson bijections provide explicit formulas for various multivariate generating functions for the oriented spanning forests which arise in this context. In this paper, we prove another important property of these bijections, namely, that it allows one to construct efficient algorithms for ranking and unranking spanning trees or spanning forests of filtered digraphs G. For example, we show that if G=(V,E) is a filtered digraph and SP(G) is the collection of spanning trees of G, then our algorithm requires O(|V|) operations of sum, difference, product, quotient, and comparison of numbers less than or equal |SP(G)| to rank or unrank spanning trees of G.

We give a canonical representation for minimal acyclic deterministic finite automata (MADFA) with n states over an alphabet of k symbols. Using this normal form, we present a method for the exact generation of MADFAs. This method avoids a rejection phase that would be needed if a generation algorithm for a larger class of objects that contains the MADFAs were used. We give upper and lower bounds for MADFAs enumeration and some exact formulas for small values of n.

We show that various aspects of k-automatic sequences — such as having an unbordered factor of length n — are both decidable and effectively enumerable. As a consequence it follows that many related sequences are either k-automatic or k-regular. These include many sequences previously studied in the literature, such as the recurrence function, the appearance function, and the repetitivity index. We also give some new characterizations of the class of k-regular sequences. Many results extend to other sequences defined in terms of Pisot numeration systems.

We describe a technique for mechanically proving certain kinds of theorems in combinatorics on words, using finite automata and a software package for manipulating them. We illustrate our technique by applying it to (a) solve an open problem of Currie and Saari on the lengths of unbordered factors in the Thue-Morse sequence; (b) verify an old result of Prodinger and Urbanek on the regular paperfolding sequence; (c) find an explicit expression for the recurrence function for the Rudin-Shapiro sequence; and (d) improve the avoidance bound in Leech's squarefree sequence. We also introduce a new measure of infinite words called condensation and compute it for some famous sequences. We follow up on the study of Currie and Saari of least periods of infinite words. We show that the characteristic sequence of least periods of a k-automatic sequence is (effectively) k-automatic. We compute the least periods for several famous sequences. Many of our results were obtained by machine computations.

We discuss the notion of privileged word, recently introduced by Kellendonk, Lenz and Savinien. A word w is privileged if it is of length ≤ 1, or has a privileged border that occurs exactly twice in w. We prove the following results: (1) if w^k is privileged for some $k\ge 1$, then w^j is privileged for all $j\ge 0$; (2) the language of privileged words is not context-free; (3) there is a linear-time algorithm to check if a given word is privileged; and (4) there are at least ${\text{2}}^{\text{n-4}}{\text{/n}}^{\text{2}}$ privileged binary words of length n.

For a formal language $L$, the problem of language enumeration asks to compute the length-lexicographically smallest word in $L$ larger than a given input $w\in {\mathrm{\Sigma }}^{\ast }$ (henceforth called the $L$-successor of $w$). We investigate this problem for regular languages from a computational complexity and state complexity perspective. We first show that if $L$ is recognized by a DFA with $n$ states, then $2^{\mathrm{\Theta }(\sqrt{nlogn})}$ states are (in general) necessary and sufficient for an unambiguous finite-state transducer to compute $L$-successors. As a byproduct, we obtain that if $L$ is recognized by a DFA with $n$ states, then $2^{\mathrm{\Theta }(\sqrt{nlogn})}$ states are sufficient for a DFA to recognize the subset $S(L)$ of $L$ composed of its lexicographically smallest words. We give a matching lower bound that holds even if $S(L)$ is represented as an NFA. It has been known that $L$-successors can be computed in polynomial time, even if the regular language is given as part of the input (assuming a suitable representation of the language, such as a DFA). In this paper, we refine this result in multiple directions. We show that if the regular language is given as part of the input and encoded as a DFA, the problem is in $NL$. If the regular language $L$ is fixed, we prove that the enumeration problem of the language is reducible to deciding membership to the Myhill-Nerode equivalence classes of $L$ under $DLOGTIME$-uniform ${AC}^0$ reductions. In particular, this implies that fixed star-free languages can be enumerated in ${AC}^0$, arbitrary fixed regular languages can be enumerated in ${NC}^1$ and that there exist regular languages for which the problem is ${NC}^1$-complete.

In this paper we design efficient algorithms for enumerating (1) the rooted trees with exactly $n$ vertices, (2) the maximal planar graphs with exactly $n$ vertices and (3) the linear extensions of a given poset. Those algorithms are based on tree structures of objects, called the family trees.

The first algorithm enumerates each ordered tree with exactly $n$ vertices in $O(1)$ time for each after $O(n)$ time preprocessing. The second algorithm enumerates each maximal planar graph with exactly $n$ vertices in $O(n^3)$ time for each on average. The third algorithm enumerates each linear extension of a given poset in $O(1)$ time for each after $O(n^2)$ time preprocessing, where $n$ is the number of the element in the set of the poset.

A personnel assignment problem is investigated when there exist no feasible assignments.

We propose algorithms to enumerate (1) regular triangulations, (2) spanning regular triangulations, (3) equivalence classes of regular triangulations with respect to symmetry, and (4) all triangulations. All of the algorithms are for arbitrary points in general dimension. They work in output-size sensitive time with memory only of several times the size of a triangulation. For the enumeration of regular triangulations, we use the fact by Gel'fand, Zelevinskii and Kapranov that regular triangulations correspond to the vertices of the secondary polytope. We use reverse search technique by Avis and Fukuda, its extension for enumerating equivalence classes of objects, and a reformulation of a maximal independent set enumeration algorithm. The last approach can be extended for enumeration of dissections.

We show that finding the simplices containing a fixed given point among those defined on a set of n points can be done in O(n + k) time for the two-dimensional case, and in O(n² + k) time for the three-dimensional case, where k is the number of these simplices.

As a byproduct, we give an alternative (to the algorithm in Ref. 4) O(n log r) algorithm that finds the red-blue boundary for n bichromatic points on the line, where r is the size of this boundary. Another byproduct is an O(n² + t) algorithm that finds the intersections of line segments having two red endpoints with those having two blue endpoints defined on a set of n bichromatic points in the plane, where t is the number of these intersections.

In this paper, we consider enumeration of geodesics on a polyhedron, where a geodesic means locally-shortest path between two points. Particularly, we consider the following preprocessing problem: given a point $s$ on a polyhedral surface and a positive real number $r$, to build a data structure that enables, for any point $t$ on the surface, to enumerate all geodesics from $s$ to $t$ whose length is less than $r$. First, we present a naive algorithm by removing the trimming process from the MMP algorithm (1987). Next, we present an improved algorithm which is practically more efficient on a non-convex polyhedron, in terms of preprocessing time and memory consumption. Moreover, we introduce a single-pair geodesic graph to succinctly encode a result of geodesic query. Lastly, we compare these naive and improved algorithms by some computer experiments.

We present an O(n log n+k log k) time and O(n+k) space algorithm which takes as input a set of n points in the plane and enumerates the k smallest distances between pairs of points in nondecreasing order. We also present an O(n log n+kn log k) solution to the problem of finding the k nearest neighbors for each of n points. Both algorithms are conceptually very simple, are easy to implement, and are based on a common data structure: the Delaunay triangulation. Variants of the algorithms work for any convex distance function metric.

We survey the problem of constructing the groups of a given finite order. We provide an extensive bibliography and outline practical algorithmic solutions to the problem. Motivated by the millennium, we used these methods to construct the groups of order at most 2000; we report on this calculation and describe the resulting group library.

Common meadows are commutative and associative algebraic structures with two operations (addition and multiplication) with additive and multiplicative identities and for which inverses are total. The inverse of zero is an error term $a$ which is absorbent for addition. We study the problem of enumerating all finite common meadows of order n (that is, common meadows with n elements). This problem turns out to be deeply connected with both the number of finite rings of order n and with the number of a certain kind of partition of positive integers.

This is the first step of the two steps to enumerate the minimal charts with two crossings. For a label $m$ of a chart $\mathrm{\Gamma }$ we denote by ${\mathrm{\Gamma }}_m$ the union of all the edges of label $m$ and their vertices. For a minimal chart $\mathrm{\Gamma }$ with exactly two crossings, we can show that the two crossings are contained in ${\mathrm{\Gamma }}_{\alpha }\cap {\mathrm{\Gamma }}_{\beta }$ for some labels $\alpha <\beta$. In this paper, we study the structure of a disk $D$ not containing any crossing but satisfying $\mathrm{\Gamma }\cap \partial D\subset {\mathrm{\Gamma }}_{\alpha +1}\cup {\mathrm{\Gamma }}_{\beta -1}$.

This paper presents two new results on the enumeration of all extreme equilibria of the sequence form of a two person extensive game. The sequence form of an extensive game is expressed, for the first time to our knowledge, as a parametric linear 0 - 1 program. Considering Ext(P) as the set of all of the sequence form extreme Nash equilibria and Ext(Q) as the set of all the parametric linear 0 - 1 program extreme points, we show that Ext(P) ⊆ Ext(Q). Using exact arithmetics classes, the algorithm EχMIP Belhaiza (2002); Audet et al. (2006) is extended to enumerate all elements of Ext(Q). A small procedure is then applied in order to obtain all elements of Ext(P).

Let $p$ be a prime and $G$ a finite $p$-group. Hall proved ${\delta }^k(G)\equiv 0(mod{p}^{d(G)-k+1})$ for $0\le k\le d(G)$, where ${\delta }^k(G)$ is the number of subgroups of index $p^k$ which do not contain the Frattini subgroup of $G$. We determine the minimal values of ${\delta }^k(G)$ for $p>2$ and ${\delta }^k(G)>0$.

We prove that a nonaffine latin quandle (also known as left distributive quasigroup) of order $2^k$ exists if and only if $k=6$ or $k\ge 8$. The construction is expressed in terms of central extensions of affine quandles.

Molecular enumeration plays a basic role in the design of drugs, which has been studied by mathematicians, computer scientists, and chemists for quite a long time. Although many researchers are involved in developing enumeration algorithms specific to drug design systems, molecular enumeration is still a hard problem to date due to its exponentially increasing large search space with larger number of atoms. To alleviate this defect, we propose efficient algorithms, BfsSimEnum and BfsMulEnum to enumerate tree-like molecules without and with multiple bonds, respectively, where chemical compounds are represented as molecular graphs. In order to reduce the large search space, we adjust some important concepts such as left-heavy, center-rooted, and normal form to molecular tree graphs. Different from many existing approaches, BfsSimEnum and BfsMulEnum firstly enumerate tree-like compounds by breadth-first search order. Computational experiments are performed to compare with several existing methods. The results suggest that our proposed methods are exact and more efficient.