Canadian Mathematical Society
  location:  Publicationsjournals
Search results

Search: MSC category 68 ( Computer science )

  Expand all        Collapse all Results 1 - 6 of 6

1. CMB Online first

Steinberg, Benjamin; van Gool, Samuel J.
Merge decompositions, two-sided Krohn-Rhodes, and aperiodic pointlikes
This paper provides short proofs of two fundamental theorems of finite semigroup theory whose previous proofs were significantly longer, namely the two-sided Krohn-Rhodes decomposition theorem and Henckell's aperiodic pointlike theorem, using a new algebraic technique that we call the merge decomposition. A prototypical application of this technique decomposes a semigroup $T$ into a two-sided semidirect product whose components are built from two subsemigroups $T_1,T_2$, which together generate $T$, and the subsemigroup generated by their setwise product $T_1T_2$. In this sense we decompose $T$ by merging the subsemigroups $T_1$ and $T_2$. More generally, our technique merges semigroup homomorphisms from free semigroups.

Keywords:Krohn-Rhodes theorem, aperiodic pointlikes
Categories:20M07, 20M35, 68Q70

2. CMB 2018 (vol 61 pp. 252)

Dewar, Megan; Pike, David; Proos, John
Connectivity in Hypergraphs
In this paper we consider two natural notions of connectivity for hypergraphs: weak and strong. We prove that the strong vertex connectivity of a connected hypergraph is bounded by its weak edge connectivity, thereby extending a theorem of Whitney from graphs to hypergraphs. We find that while determining a minimum weak vertex cut can be done in polynomial time and is equivalent to finding a minimum vertex cut in the 2-section of the hypergraph in question, determining a minimum strong vertex cut is NP-hard for general hypergraphs. Moreover, the problem of finding minimum strong vertex cuts remains NP-hard when restricted to hypergraphs with maximum edge size at most 3. We also discuss the relationship between strong vertex connectivity and the minimum transversal problem for hypergraphs, showing that there are classes of hypergraphs for which one of the problems is NP-hard while the other can be solved in polynomial time.

Keywords:hypergraph, connectivity, computational complexity, transversal
Categories:05C65, 05C40, 68Q17

3. CMB 2017 (vol 61 pp. 40)

Chen, Wengu; Ge, Huanmin
A sharp bound on RIC in generalized orthogonal matching pursuit
Generalized orthogonal matching pursuit (gOMP) algorithm has received much attention in recent years as a natural extension of orthogonal matching pursuit (OMP). It is used to recover sparse signals in compressive sensing. In this paper, a new bound is obtained for the exact reconstruction of every $K$-sparse signal via the gOMP algorithm in the noiseless case. That is, if the restricted isometry constant (RIC) $\delta_{NK+1}$ of the sensing matrix $A$ satisfies $ \delta_{NK+1}\lt \frac{1}{\sqrt{\frac{K}{N}+1}}$, then the gOMP can perfectly recover every $K$-sparse signal $x$ from $y=Ax$. Furthermore, the bound is proved to be sharp. In the noisy case, the above bound on RIC combining with an extra condition on the minimum magnitude of the nonzero components of $K$-sparse signals can guarantee that the gOMP selects all of support indices of the $K$-sparse signals.

Keywords:sensing matrix, generalized orthogonal matching pursuit, restricted isometry constant, sparse signal
Categories:65D15, 65J22, 68W40

4. CMB 2011 (vol 54 pp. 566)

Zhou, Xiang-Jun; Shi, Lei; Zhou, Ding-Xuan
Non-uniform Randomized Sampling for Multivariate Approximation by High Order Parzen Windows
We consider approximation of multivariate functions in Sobolev spaces by high order Parzen windows in a non-uniform sampling setting. Sampling points are neither i.i.d. nor regular, but are noised from regular grids by non-uniform shifts of a probability density function. Sample function values at sampling points are drawn according to probability measures with expected values being values of the approximated function. The approximation orders are estimated by means of regularity of the approximated function, the density function, and the order of the Parzen windows, under suitable choices of the scaling parameter.

Keywords:multivariate approximation, Sobolev spaces, non-uniform randomized sampling, high order Parzen windows, convergence rates
Categories:68T05, 62J02

5. CMB 2011 (vol 54 pp. 288)

Jacobs, David P.; Rayes, Mohamed O.; Trevisan, Vilmar
The Resultant of Chebyshev Polynomials
Let $T_{n}$ denote the $n$-th Chebyshev polynomial of the first kind, and let $U_{n}$ denote the $n$-th Chebyshev polynomial of the second kind. We give an explicit formula for the resultant $\operatorname{res}( T_{m}, T_{n} )$. Similarly, we give a formula for $\operatorname{res}( U_{m}, U_{n} )$.

Keywords:resultant, Chebyshev polynomial
Categories:11Y11, 68W20

6. CMB 2004 (vol 47 pp. 343)

Drensky, Vesselin; Hammoudi, Lakhdar
Combinatorics of Words and Semigroup Algebras Which Are Sums of Locally Nilpotent Subalgebras
We construct new examples of non-nil algebras with any number of generators, which are direct sums of two locally nilpotent subalgebras. Like all previously known examples, our examples are contracted semigroup algebras and the underlying semigroups are unions of locally nilpotent subsemigroups. In our constructions we make more transparent than in the past the close relationship between the considered problem and combinatorics of words.

Keywords:locally nilpotent rings,, nil rings, locally nilpotent semigroups,, semigroup algebras, monomial algebras, infinite words
Categories:16N40, 16S15, 20M05, 20M25, 68R15

© Canadian Mathematical Society, 2018 :