Narrow Results

A semigroup S is said to be ℓ-threshold k-testable if it satisfies all identities u = v where u, v is an arbitrary pair of words over a finite alphabet Σ such that they simultaneously belong or fail to belong to any ℓ-threshold k-testable (regular) language. We give an asymptotic formula for the free spectrum of the variety of all ℓ-threshold k-testable semigroups, thereby providing an asymptotic upper bound on the size of an arbitrary finitely generated locally threshold testable semigroup. The combinatorial interpretation of this task yields an enumeration problem for particular edge labelings of de Bruijn graphs.

A cluttered ordering is a type of a cyclic ordering of a graph. It can provide minimize the number of disk operations. Mueller et al. (2005) decomposed the complete bipartite graph into isomorphic copies of the special bipartite graph H(h; t), where h and t are positive integers. They presented some edge labeling of the infinite families of H(1; t), H(2; t). Adachi (2017) defined the special bipartite graph H(h, k; t), which is extension of H(h; t), and presented some edge labeling of the infinite families of H(1, 2; t). In this paper, we investigate the case of H(1, k; t), and obtain the corresponding cluttered orderings.