Classifiers can be combined to reduce classification errors. We did experiments on a data set consisting of different sets of features of handwritten digits. Different types of classifiers were trained on these feature sets. The performances of these classifiers and combination rules were tested. The best results were acquired with the mean, median and product combination rules. The product was best for combining linear classifiers, the median for $k$-NN classifiers. Training a classifier on all features...

Let $ϵ=({ϵ}_n{)}_{n\ge 0}$ be the Thue-Morse sequence, i.e., the sequence defined by the recurrence equations:$${ϵ}_0=1,{ϵ}_{2n}={ϵ}_n,{ϵ}_{2n+1}=1-{ϵ}_n.$$We consider $\left\{\right|{ℰ}_n^p|{\}}_{n\ge 1,p\ge 0}$, the double sequence of Hankel determinants (modulo 2) associated with the Thue-Morse sequence. Together with three other sequences, it obeys a set of sixteen recurrence equations. It is shown to be automatic. Applications are given, namely to combinatorial properties of the Thue-Morse sequence and to the existence of certain Padé approximants of the power series ${\sum }_{n\ge 0}(-1{)}^{{ϵ}_n}{x}^n$.

Let ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{k\to d}$ be the following algorithmic problem: Given a finite simplicial complex $K$ of dimension at most $k$, does there exist a (piecewise linear) embedding of $K$ into ${ℝ}^d$? Known results easily imply polynomiality of ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{k\to 2}$ ($k=1,2$; the case $k=1,d=2$ is graph planarity) and of ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{k\to 2k}$ for all $k\ge 3$. We show that the celebrated result of Novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{d\to d}$ and ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{(d-1)\to d}$ are undecidable for each ${}_d\ge 5$. Our main result is NP-hardness of ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{2\to 4}$ and, more generally, of ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{k\to d}$ for all $k$, $d$ with...

A total-colored path is total rainbow if both its edges and internal vertices have distinct colors. The total rainbow connection number of a connected graph G, denoted by trc(G), is the smallest number of colors that are needed in a total-coloring of G in order to make G total rainbow connected, that is, any two vertices of G are connected by a total rainbow path. In this paper, we study the computational complexity of total rainbow connection of graphs. We show that deciding whether a given total-coloring...

This work has been partially supported by Grant No. DO 02-275, 16.12.2008, Bulgarian NSF, Ministry of Education and Science.Hausdorff distance (HD) seems the most efficient instrument for measuring how far two compact non-empty subsets of a metric space are from each other. This paper considers the possibilities provided by HD and some of its modifications used recently by many authors for resemblance between binary text images. Summarizing part of the existing word image matching methods, relied...

Let $𝒫$ be a hereditary property of words, i.e., an infinite class of finite words such that every subword (block) of a word belonging to $𝒫$ is also in $𝒫$. Extending the classical Morse-Hedlund theorem, we show that either $𝒫$ contains at least $n+1$ words of length $n$ for every $n$ or, for some $N$, it contains at most $N$ words of length $n$ for every $n$. More importantly, we prove the following quantitative extension of this result: if $𝒫$ has $m\le n$ words of length $n$ then, for every $k\ge n+m$, it contains at most $\lceil (m+1)/2\rceil \lfloor (m+1)/2\rfloor$ words of length...

Let P be a hereditary property of words, i.e., an infinite class of finite words such that every subword (block) of a word belonging to P is also in P. Extending the classical Morse-Hedlund theorem, we show that either P contains at least n+1 words of length n for every n or, for some N, it contains at most N words of length n for every n. More importantly, we prove the following quantitative extension of this result: if P has m ≤ n words of length n then, for every k ≥ n + m, it contains at most...

The notion of treewidth is of considerable interest in relation to NP-hard problems. Indeed, several studies have shown that the tree-decomposition method can be used to solve many basic optimization problems in polynomial time when treewidth is bounded, even if, for arbitrary graphs, computing the treewidth is NP-hard. Several papers present heuristics with computational experiments. For many graphs the discrepancy between the heuristic results and the best lower bounds is still very large. The...

The notion of treewidth is of considerable interest in relation to NP-hard problems. Indeed, several studies have shown that the tree-decomposition method can be used to solve many basic optimization problems in polynomial time when treewidth is bounded, even if, for arbitrary graphs, computing the treewidth is NP-hard. Several papers present heuristics with computational experiments. For many graphs the discrepancy between the heuristic results and the best lower bounds is still very large....