Search results for "Computation Theory & Mathematics"
showing 10 items of 332 documents
Groups with few $p'$-character degrees
2019
Abstract We prove a variation of Thompson's Theorem. Namely, if the first column of the character table of a finite group G contains only two distinct values not divisible by a given prime number p > 3 , then O p p ′ p p ′ ( G ) = 1 . This is done by using the classification of finite simple groups.
Non-vanishing elements of finite groups
2010
AbstractLet G be a finite group, and let Irr(G) denote the set of irreducible complex characters of G. An element x of G is non-vanishing if, for every χ in Irr(G), we have χ(x)≠0. We prove that, if x is a non-vanishing element of G and the order of x is coprime to 6, then x lies in the Fitting subgroup of G.
A Feature Rich Distance-Based Many-Objective Visualisable Test Problem Generator
2019
In optimiser analysis and design it is informative to visualise how a search point/population moves through the design space over time. Visualisable distance-based many-objective optimisation problems have been developed whose design space is in two-dimensions with arbitrarily many objective dimensions. Previous work has shown how disconnected Pareto sets may be formed, how problems can be projected to and from arbitrarily many design dimensions, and how dominance resistant regions of design space may be defined. Most recently, a test suite has been proposed using distances to lines rather than points. However, active use of visualisable problems has been limited. This may be because the ty…
On the relative sizes of learnable sets
1998
Abstract Measure and category (or rather, their recursion-theoretical counterparts) have been used in theoretical computer science to make precise the intuitive notion “for most of the recursive sets”. We use the notions of effective measure and category to discuss the relative sizes of inferrible sets, and their complements. We find that inferable sets become large rather quickly in the standard hierarchies of learnability. On the other hand, the complements of the learnable sets are all large.
2D motif basis applied to the classification of digital images
2016
The classification of raw data often involves the problem of selecting the appropriate set of features to represent the input data. Different types of features can be extracted from the input dataset, but only some of them are actually relevant for the classification process. Since relevant features are often unknown in real-world problems, many candidate features are usually introduced. This degrades both the speed and the predictive accuracy of the classifier due to the presence of redundancy in the set of candidate features. Recently, a special class of bidimensional motifs, i.e. 2D motif basis has been introduced in the literature. 2D motif basis showed to be powerful in capturing the r…
Exact results for accepting probabilities of quantum automata
2001
One of the properties of Kondacs-Watrous model of quantum finite automata (QFA) is that the probability of the correct answer for a QFA cannot be amplified arbitrarily. In this paper, we determine the maximum probabilities achieved by QFAs for several languages. In particular, we show that any language that is not recognized by an RFA (reversible finite automaton) can be recognized by a QFA with probability at most 0.7726...
Word assembly through minimal forbidden words
2006
AbstractWe give a linear-time algorithm to reconstruct a finite word w over a finite alphabet A of constant size starting from a finite set of factors of w verifying a suitable hypothesis. We use combinatorics techniques based on the minimal forbidden words, which have been introduced in previous papers. This improves a previous algorithm which worked under the assumption of stronger hypothesis.
The pruning-grafting lattice of binary trees
2008
AbstractWe introduce a new lattice structure Bn on binary trees of size n. We exhibit efficient algorithms for computing meet and join of two binary trees and give several properties of this lattice. More precisely, we prove that the length of a longest (resp. shortest) path between 0 and 1 in Bn equals to the Eulerian numbers 2n−(n+1) (resp. (n−1)2) and that the number of coverings is (2nn−1). Finally, we exhibit a matching in a constructive way. Then we propose some open problems about this new structure.
From Nerode's congruence to Suffix Automata with mismatches
2009
AbstractIn this paper we focus on the minimal deterministic finite automaton Sk that recognizes the set of suffixes of a word w up to k errors. As first result we give a characterization of the Nerode’s right-invariant congruence that is associated with Sk. This result generalizes the classical characterization described in [A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. Chen, J. Seiferas, The smallest automaton recognizing the subwords of a text, Theoretical Computer Science, 40, 1985, 31–55]. As second result we present an algorithm that makes use of Sk to accept in an efficient way the language of all suffixes of w up to k errors in every window of size r of a text, where r is the…
On the exhaustive generation of k-convex polyominoes
2017
The degree of convexity of a convex polyomino P is the smallest integer k such that any two cells of P can be joined by a monotone path inside P with at most k changes of direction. In this paper we present a simple algorithm for computing the degree of convexity of a convex polyomino and we show how it can be used to design an algorithm that generates, given an integer k, all k-convex polyominoes of area n in constant amortized time, using space O(n). Furthermore, by applying few changes, we are able to generate all convex polyominoes whose degree of convexity is exactly k.