Search results for "combinatoric"
showing 10 items of 1776 documents
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].
Countable connected spaces and bunches of arcs in R3
2006
Abstract We investigate the images (also called quotients) of countable connected bunches of arcs in R 3 , obtained by shrinking the arcs to points (see Section 2 for definitions of new terms). First, we give an intrinsic description of such images among T 1 -spaces: they are precisely countable and weakly first countable spaces. Moreover, an image is first countable if and only if it can be represented as a quotient of another bunch with its projection hereditarily quotient (Theorem 2.7). Applying this result we see, for instance, that two classical countable connected T 2 -spaces—the Bing space [R.H. Bing, A connected countable Hausdorff space, Proc. Amer. Math. Soc. 4 (1953) 474], and th…
Some local properties defining $\mathcal T_0$-groups and related classes of groups
2016
We call $G$ a $\operatorname{Hall}_{\mathcal X}$-group if there exists a normal nilpotent subgroup $N$ of $G$ for which $G/N'$ is an ${\mathcal X}$-group. We call $G$ a ${\mathcal T}_0$-group provided $G/\Phi(G)$ is a ${\mathcal T}$-group, that is, one in which normality is a transitive relation. We present several new local classes of groups which locally define $\operatorname{Hall}_{\mathcal X}$-groups and ${\mathcal T}_0$-groups where ${\mathcal X}\in\{ {\mathcal T},\mathcal {PT},\mathcal {PST}\}$; the classes $\mathcal {PT}$ and $\mathcal {PST}$ denote, respectively, the classes of groups in which permutability and S-permutability are transitive relations.
Equations on trees
1996
We introduce the notion of equation on trees, generalizing the corresponding notion for words, and we develop the first steps of a theory of tree equations. The main result of the paper states that, if a pair of trees is the solution of a tree equation with two indeterminates, then the two trees are both powers of the same tree. As an application, we show that a tree can be expressed in a unique way as a power of a primitive tree. This extends a basic result of combinatorics on words to trees. Some open problems are finally proposed.
Frequency Assignment and Multicoloring Powers of Square and Triangular Meshes
2005
The static frequency assignment problem on cellular networks can be abstracted as a multicoloring problem on a weighted graph, where each vertex of the graph is a base station in the network, and the weight associated with each vertex represents the number of calls to be served at the vertex. The edges of the graph model interference constraints for frequencies assigned to neighboring stations. In this paper, we first propose an algorithm to multicolor any weighted planar graph with at most $\frac{11}{4}W$ colors, where W denotes the weighted clique number. Next, we present a polynomial time approximation algorithm which garantees at most 2W colors for multicoloring a power square mesh. Fur…
Graph Connectivity, Monadic NP and built-in relations of moderate degree
1995
It has been conjectured [FSV93] that an existential secondoder formula, in which the second-order quantification is restricted to unary relations (i.e. a Monadic NP formula), cannot express Graph Connectivity even in the presence of arbitrary built-in relations.
Automorphism groups of some affine and finite type Artin groups
2004
We observe that, for fixed n ≥ 3, each of the Artin groups of finite type An, Bn = Cn, and affine type ˜ An−1 and ˜ Cn−1 is a central extension of a finite index subgroup of the mapping class group of the (n + 2)-punctured sphere. (The centre is trivial in the affine case and infinite cyclic in the finite type cases). Using results of Ivanov and Korkmaz on abstract commensurators of surface mapping class groups we are able to determine the automorphism groups of each member of these four infinite families of Artin groups. A rank n Coxeter matrix is a symmetric n × n matrix M with integer entries mij ∈ N ∪ {∞} where mij ≥ 2 for ij, and mii = 1 for all 1 ≤ i ≤ n. Given any rank n Coxeter matr…