Search results for "Combinatorics"
showing 10 items of 1770 documents
Finite Soluble Groups with Permutable Subnormal Subgroups
2001
Abstract A finite group G is said to be a PST -group if every subnormal subgroup of G permutes with every Sylow subgroup of G . We shall discuss the normal structure of soluble PST -groups, mainly defining a local version of this concept. A deep study of the local structure turns out to be crucial for obtaining information about the global property. Moreover, a new approach to soluble PT -groups, i.e., soluble groups in which permutability is a transitive relation, follows naturally from our vision of PST -groups. Our techniques and results provide a unified point of view for T -groups, PT -groups, and PST -groups in the soluble universe, showing that the difference between these classes is…
On the Construction of Classes of Suffix Trees for Square Matrices: Algorithms and Applications
1996
AbstractWe provide a uniform framework for the study of index data structures for a two-dimensional matrixTEXT[1:n, 1:n] whose entries are drawn from an ordered alphabetΣ. An index forTEXTcan be informally seen as the two-dimensional analog of the suffix tree for a string. It allows on-line searches and statistics to be performed onTEXTby representing compactly theΘ(n3) square submatrices ofTEXTin optimalO(n2) space. We identify 4n−1families of indices forTEXT, each containing ∏ni=1(2i−1)! isomorphic data structures. We also develop techniques leading to a single algorithm that efficiently builds any index in any family inO(n2logn) time andO(n2) space. Such an algorithm improves in various …
Superposition in Classes of Ultradifferentiable Functions
2006
We present a complete characterization of the classes of ultradifferentiable functions that are holomorphically closed. Moreover, we show that any class holomorphically closed is also closed under composition (now without restrictions on the number of variables). In this case, we also discuss continuity and differentiability properties of the non-linear superposition operator g → f ◦ g.
Polynomial identities for the Jordan algebra of a degenerate symmetric bilinear form
2013
Let J(n) be the Jordan algebra of a degenerate symmetric bilinear form. In the first section we classify all possible G-gradings on J(n) where G is any group, while in the second part we restrict our attention to a degenerate symmetric bilinear form of rank n - 1, where n is the dimension of the vector space V defining J(n). We prove that in this case the algebra J(n) is PI-equivalent to the Jordan algebra of a nondegenerate bilinear form.
Standard Sturmian words and automata minimization algorithms
2015
The study of some close connections between the combinatorial properties of words and the performance of the automata minimization process constitutes the main focus of this paper. These relationships have been, in fact, the basis of the study of the tightness and the extremal cases of Hopcroft's algorithm, that is, up to now, the most efficient minimization method for deterministic finite state automata. Recently, increasing attention has been paid to another minimization method that, unlike the approach proposed by Hopcroft, is not based on refinement of the set of states of the automaton, but on automata operations such as determinization and reverse, and is also applicable to non-determ…
Extremal minimality conditions on automata
2012
AbstractIn this paper we investigate the minimality problem of DFAs by varying the set of final states. In other words, we are interested on how the choice of the final states can affect the minimality of the automata. The state-pair graph is a useful tool to investigate such a problem. The choice of a set of final states for the automaton A defines a coloring of the closed components of the state-pair graph and the minimality of A corresponds to a property of these colored components. A particular attention is devoted to the analysis of some extremal cases such as, for example, the automata that are minimal for any choice of the subset of final states F from the state set Q of the automato…
Automata with Extremal Minimality Conditions
2010
It is well known that the minimality of a deterministic finite automaton (DFA) depends on the set of final states. In this paper we study the minimality of a strongly connected DFA by varying the set of final states. We consider, in particular, some extremal cases. A strongly connected DFA is called uniformly minimal if it is minimal, for any choice of the set of final states. It is called never-minimal if it is not minimal, for any choice of the set of final states. We show that there exists an infinite family of uniformly minimal automata and that there exists an infinite family of never-minimal automata. Some properties of these automata are investigated and, in particular, we consider t…
A graph theoretic approach to automata minimality
2012
AbstractThe paper presents a graph-theoretic approach to test the minimality of a deterministic automaton. In particular, we focus on problems concerning the dependence of the minimality of an automaton on the choice of the set F of final states or on the cardinality of the set F. We introduce different minimality conditions of an automaton and show that such conditions can be characterized in graph-theoretic terms.
On Extremal Cases of Hopcroft’s Algorithm
2009
In this paper we consider the problem of minimization of deterministic finite automata (DFA) with reference to Hopcroft’s algorithm. Hopcroft’s algorithm has several degrees of freedom, so there can exist different sequences of refinements of the set of the states that lead to the final partition. We find an infinite family of binary automata for which such a process is unique. Some recent papers (cf. [3,7,1]) have been devoted to find families of automata for which Hopcroft’s algorithm has its worst execution time. They are unary automata associated to circular words. However, automata minimization can be achieved also in linear time when the alphabet has only one letter (cf. [14]), so in …
Minimal nontrivial space complexity of probabilistic one- way turing machines
2005
Languages recognizable in o(log log n) space by probabilistic one — way Turing machines are proved to be regular. This solves an open problem in [4].