Search results for "Combinatorics"
showing 10 items of 1770 documents
A Logical Characterisation of Linear Time on Nondeterministic Turing Machines
1999
The paper gives a logical characterisation of the class NTIME(n) of problems that can be solved on a nondeterministic Turing machine in linear time. It is shown that a set L of strings is in this class if and only if there is a formula of the form ∃f1..∃fk∃R1..∃Rm∀xφv; that is true exactly for all strings in L. In this formula the fi are unary function symbols, the Ri are unary relation symbols and φv; is a quantifierfree formula. Furthermore, the quantification of functions is restricted to non-crossing, decreasing functions and in φv; no equations in which different functions occur are allowed. There are a number of variations of this statement, e.g., it holds also for k = 3. From these r…
Hopcroft’s Algorithm and Cyclic Automata
2008
Minimization of deterministic finite automata is a largely studied problem of the Theory of Automata and Formal Languages. It consists in finding the unique (up to isomorphism) minimal deterministic automaton recognizing a set of words. The first approaches to this topic can be traced back to the 1950’s with the works of Huffman and Moore (cf. [12,15]). Over the years several methods to solve this problem have been proposed but the most efficient algorithm in the worst case was given by Hopcroft in [11]. Such an algorithm computes in O(n log n) the minimal automaton equivalent to a given automaton with n states. The Hopcroft’s algorithm has been widely studied, described and implemented by …
Hopcroft's algorithm and tree-like automata
2011
Minimizing a deterministic finite automata (DFA) is a very important problem in theory of automata and formal languages. Hopcroft's algorithm represents the fastest known solution to the such a problem. In this paper we analyze the behavior of this algorithm on a family binary automata, called tree-like automata, associated to binary labeled trees constructed by words. We prove that all the executions of the algorithm on tree-like automata associated to trees, constructed by standard words, have running time with the same asymptotic growth rate. In particular, we provide a lower and upper bound for the running time of the algorithm expressed in terms of combinatorial properties of the trees…
C-Supplemented subgroups of finite groups
2000
A subgroup H of a group G is said to be c-supplemented in G if there exists a subgroup K of G such that HKa G and H\ K is contained in CoreGOHU .W e follow Hall's ideas to characterize the structure of the finite groups in which every subgroup is c-supplemented. Properties of c-supplemented subgroups are also applied to determine the structure of some finite groups.
Rademacher Theorem for Fréchet spaces
2010
Abstract Let X be a separable Frechet space. In this paper we define a class A of null sets in X that is properly contained in the class of Aronszajn null sets, and we prove that a Lipschitz map from an open subset of X into a Gelfand-Frechet space is Gateaux differentiable outside a set belonging to A. This is an extension to Frechet spaces of a result (see [PZ]) due to D. Preiss and L. Zajicek.
On the Russo-Dye Theorem for positive linear maps
2019
Abstract We revisit a classical result, the Russo-Dye Theorem, stating that every positive linear map attains its norm at the identity.
Some properties of [tr(Q2p)]12p with application to linear minimax estimation
1990
Abstract A nondifferentiable minimization problem is considered which occurs in linear minimax estimation. This problem is solved by replacing the nondifferentiable maximal eigenvalue of a real nonnegative definite matrix Q with [tr( Q 2 p )] 1/2 p . It is shown that any descent algorithm with inexact step-length rule can be used to obtain linear minimax estimators for the parameter vector of a parameter-restricted linear model.
The structure of the state representation of shift invariant controllable and observable group codes
2000
AbstractIn this paper an investigation on the structure of the canonical trellis section of shift invariant, l-controllable and m-observable group codes is carried out. Necessary and sufficient conditions for a set of group homomorphisms in order that they represent the trellis section of this class of codes are established.
The Rotation χ-Lattice of Ternary Trees
2001
This paper generalizes to k-ary trees the well-known rotation transformation on binary trees. For brevity, only the ternary case is developped. The rotation on ternary trees is characterized using some codings of trees. Although the corresponding poset is not a lattice, we show that it is a χ-lattice in the sense of Leutola–Nieminen. Efficient algorithms are exhibited to compute meets and joins choosen in a particular way.
On the Bishop–Phelps–Bollobás theorem for multilinear mappings
2017
Abstract We study the Bishop–Phelps–Bollobas property and the Bishop–Phelps–Bollobas property for numerical radius. Our main aim is to extend some known results about norm or numerical radius attaining operators to multilinear and polynomial cases. We characterize the pair ( l 1 ( X ) , Y ) to have the BPBp for bilinear forms and prove that on L 1 ( μ ) the numerical radius and the norm of a multilinear mapping are the same. We also show that L 1 ( μ ) fails the BPBp-nu for multilinear mappings although L 1 ( μ ) satisfies it in the operator case for every measure μ.