On the property of probabilistic context-free grammars.
On the quantum chromatic number of a graph.
On the recognition of bipolarizable and -simplicial graphs.
On the recognizability of self-generating sets.
On the reduction of a random basis
For p ≤ n, let b1(n),...,bp(n) be independent random vectors in with the same distribution invariant by rotation and without mass at the origin. Almost surely these vectors form a basis for the Euclidean lattice they generate. The topic of this paper is the property of reduction of this random basis in the sense of Lenstra-Lenstra-Lovász (LLL). If is the basis obtained from b1(n),...,bp(n) by Gram-Schmidt orthogonalization, the quality of the reduction depends upon the sequence of ratios...
On the regularity of edges in image segmentation
On the resolvent of an ideal and some applications.
On the restricted equivalence for subclasses of propositional logic
On the robustness of ALMOST-
On the role of configurations in the theory of grammars
On the semidirect product of the pseudovariety of semilattices by a locally finite pseudovariety of groups
On the separating power of EOL systems
On the shape parameter and constrained modification of GB-spline curves.
On the simplest centralizer of a language
Given a finite alphabet Σ and a language L ⊆ ∑+, the centralizer of L is defined as the maximal language commuting with it. We prove that if the primitive root of the smallest word of L (with respect to a lexicographic order) is prefix distinguishable in L then the centralizer of L is as simple as possible, that is, the submonoid L*. This lets us obtain a simple proof of a known result concerning the centralizer of nonperiodic three-word languages.
On the singular decomposition of matrices.
On the size of context-free grammars
On the size of DeRemer's analyzers
On the size of minimal unsatisfiable formulas.
On the size of one-way quantum finite automata with periodic behaviors
We show that, for any stochastic event of period , there exists a measure-once one-way quantum finite automaton (1qfa) with at most states inducing the event , for constants , , satisfying . This fact is proved by designing an algorithm which constructs the desired 1qfa in polynomial time. As a consequence, we get that any periodic language of period can be accepted with isolated cut point by a 1qfa with no more than states. Our results give added evidence of the strength of measure-once...
On the Size of One-way Quantum Finite Automata with Periodic Behaviors
We show that, for any stochastic event p of period n, there exists a measure-once one-way quantum finite automaton (1qfa) with at most states inducing the event ap+b, for constants a>0, b ≥ 0, satisfying a+b ≥ 1. This fact is proved by designing an algorithm which constructs the desired 1qfa in polynomial time. As a consequence, we get that any periodic language of period n can be accepted with isolated cut point by a 1qfa with no more than states. Our results give added evidence of the...