A PAC teaching model – under helpful distributions – is proposed which introduces the classical ideas of teaching models within the PAC setting: a polynomial-sized teaching set is associated with each target concept; the criterion of success is PAC identification; an additional parameter, namely the inverse of the minimum probability assigned to any example in the teaching set, is associated with each distribution; the learning algorithm running time takes this new parameter into account. An Occam...

A PAC teaching model -under helpful distributions -is proposed which introduces the classical ideas of teaching models within the PAC setting: a polynomial-sized teaching set is associated with each target concept; the criterion of success is PAC identification; an additional parameter, namely the inverse of the minimum probability assigned to any example in the teaching set, is associated with each distribution; the learning algorithm running time takes this new parameter into account. ...

The MATRIX PACKING DOWN problem asks to find a row permutation of a given (0,1)-matrix in such a way that the total sum of the first non-zero column indexes is maximized. We study the computational complexity of this problem. We prove that the MATRIX PACKING DOWN problem is NP-complete even when restricted to zero trace symmetric (0,1)-matrices or to (0,1)-matrices with at most two 1's per column. Also, as intermediate results, we introduce several new simple graph layout problems which...

We present an implemented algorithmic method for counting and isolating all p-adic roots of univariate polynomials f over the rational numbers. The roots of f are uniquely described by p-adic isolating balls, that can be refined to any desired precision; their p-adic distances are also computed precisely. The method is polynomial space in all input data including the prime p. We also investigate the uniformity of the method with respect to the coefficients of f and the primes p. Our method thus...

We study infinite words u over an alphabet $𝒜$ satisfying the property $𝒫:𝒫\left(n\right)+𝒫(n+1)=1+\#𝒜\mathrm{for}\mathrm{any}n\in \mathbb{N}$, where $𝒫\left(n\right)$ denotes the number of palindromic factors of length n occurring in the language of u. We study also infinite words satisfying a stronger property $\mathrm{𝒫ℰ}$: every palindrome of u has exactly one palindromic extension in u. For binary words, the properties $𝒫$ and $\mathrm{𝒫ℰ}$ coincide and these properties characterize Sturmian words, i.e., words with the complexity C(n) = n + 1 for any $n\in \mathbb{N}$. In this paper, we focus on ternary infinite...

We study the palindromic complexity of infinite words $u_{\beta }$, the fixed points of the substitution over a binary alphabet, $\varphi \left(0\right)=0^{a}1$, $\varphi \left(1\right)=0^{b}1$, with $a-1\ge b\ge 1$, which are canonically associated with quadratic non-simple Parry numbers $\beta$.

We study the palindromic complexity of infinite words uβ, the fixed points of the substitution over a binary alphabet, φ(0) = 0a1, φ(1) = 0b1, with a - 1 ≥ b ≥ 1, which are canonically associated with quadratic non-simple Parry numbers β.

A simple Parry number is a real number $\beta \>1$ such that the Rényi expansion of $1$ is finite, of the form $d_{\beta }\left(1\right)=t_1\cdots t_m$. We study the palindromic structure of infinite aperiodic words $u_{\beta }$ that are the fixed point of a substitution associated with a simple Parry number $\beta$. It is shown that the word $u_{\beta }$ contains infinitely many palindromes if and only if $t_1=t_2=\cdots =t_{m-1}\ge t_m$. Numbers $\beta$ satisfying this condition are the so-called confluent Pisot numbers. If $t_m=1$ then $u_{\beta }$ is an Arnoux-Rauzy word. We show that if $\beta$ is a confluent Pisot number then...

In the present work, we investigate real numbers whose sequence of partial quotients enjoys some combinatorial properties involving the notion of palindrome. We provide three new transendence criteria, that apply to a broad class of continued fraction expansions, including expansions with unbounded partial quotients. Their proofs heavily depend on the Schmidt Subspace Theorem.

A generalization of the spatially one-dimensional parallel pipe-line algorithm for solution of the initial-boundary-value problem using explicit difference method to the two-dimensional case is presented. The suggested algorithm has been verified by implementation on a workstation-cluster running under PVM (Parallel Virtual Machine). Theoretical estimates of the speed-up are presented.

We present parallel algorithms on the BSP/CGM model, with p processors, to count and generate all the maximal cliques of a circle graph with n vertices and m edges. To count the number of all the maximal cliques, without actually generating them, our algorithm requires O(log p) communication rounds with O(nm/p) local computation time. We also present an algorithm to generate the first maximal clique in O(log p) communication rounds with O(nm/p) local computation, and to generate each one of...

We consider the parallel approximability of two problems arising from high multiplicity scheduling, namely the unweighted model with variable processing requirements and the weighted model with identical processing requirements. These two problems are known to be modelled by a class of quadratic programs that are efficiently solvable in polynomial time. On the parallel setting, both problems are P-complete and hence cannot be efficiently solved in parallel unless P = NC. To deal with the parallel...

We consider the parallel approximability of two problems arising from high multiplicity scheduling, namely the unweighted model with variable processing requirements and the weighted model with identical processing requirements. These two problems are known to be modelled by a class of quadratic programs that are efficiently solvable in polynomial time. On the parallel setting, both problems are P-complete and hence cannot be efficiently solved in parallel unless P = NC. To deal with the parallel...

Mitrion-C based implementations of three image processing algorithms: a look-up table operation, simple local thresholding and Sauvola's local thresholding are described. Implementation results, performance of the design and FPGA logic utilization are discussed.