Search results for "complex"
showing 10 items of 5889 documents
On the Class of Languages Recognizable by 1-Way Quantum Finite Automata
2007
It is an open problem to characterize the class of languages recognized by quantum finite automata (QFA). We examine some necessary and some sufficient conditions for a (regular) language to be recognizable by a QFA. For a subclass of regular languages we get a condition which is necessary and sufficient. Also, we prove that the class of languages recognizable by a QFA is not closed under union or any other binary Boolean operation where both arguments are significant.
Quantum Finite Automata and Probabilistic Reversible Automata: R-trivial Idempotent Languages
2011
We study the recognition of R-trivial idempotent (R1) languages by various models of "decide-and-halt" quantum finite automata (QFA) and probabilistic reversible automata (DH-PRA). We introduce bistochastic QFA (MM-BQFA), a model which generalizes both Nayak's enhanced QFA and DH-PRA. We apply tools from algebraic automata theory and systems of linear inequalities to give a complete characterization of R1 languages recognized by all these models. We also find that "forbidden constructions" known so far do not include all of the languages that cannot be recognized by measure-many QFA.
Postselection Finite Quantum Automata
2010
Postselection for quantum computing devices was introduced by S. Aaronson[2] as an excitingly efficient tool to solve long standing problems of computational complexity related to classical computing devices only. This was a surprising usage of notions of quantum computation. We introduce Aaronson's type postselection in quantum finite automata. There are several nonequivalent definitions of quantumfinite automata. Nearly all of them recognize only regular languages but not all regular languages. We prove that PALINDROMES can be recognized by MM-quantum finite automata with postselection. At first we prove by a direct construction that the complement of this language can be recognized this …
Finite Groups with Only One NonLinear Irreducible Representation
2012
Let 𝕂 be an algebraically closed field. We classify the finite groups having exactly one irreducible 𝕂-representation of degree bigger than one. The case where the characteristic of 𝕂 is zero, was done by G. Seitz in 1968.
Ordinary and graded cocharacter of the Jordan algebra of 2x2 upper triangular matrices
2014
Abstract Let F be a field of characteristic zero and U J 2 ( F ) be the Jordan algebra of 2 × 2 upper triangular matrices over F . In this paper we give a complete description of the space of multilinear graded and ordinary identities in the language of Young diagrams through the representation theory of a Young subgroup of S n . For every Z 2 -grading of U J 2 ( F ) we compute the multiplicities in the graded cocharacter sequence and furthermore we compute the ordinary cocharacter.
Extending Brauer's Height Zero Conjecture to Blocks with Nonabelian Defect Groups
2013
We propose a generalization of Brauer?s Height Zero Conjecture that considers positive heights. We give strong evidence supporting one half of the generalization and obtain some partial results regarding the other half.
The Monadic Quantifier Alternation Hierarchy over Grids and Graphs
2002
AbstractThe monadic second-order quantifier alternation hierarchy over the class of finite graphs is shown to be strict. The proof is based on automata theoretic ideas and starts from a restricted class of graph-like structures, namely finite two-dimensional grids. Considering grids where the width is a function of the height, we prove that the difference between the levels k+1 and k of the monadic hierarchy is witnessed by a set of grids where this function is (k+1)-fold exponential. We then transfer the hierarchy result to the class of directed (or undirected) graphs, using an encoding technique called strong reduction. It is notable that one can obtain sets of graphs which occur arbitrar…
Polynomial codimension growth and the Specht problem
2017
Abstract We construct a continuous family of algebras over a field of characteristic zero with slow codimension growth bounded by a polynomial of degree 4. This is achieved by building, for any real number α ∈ ( 0 , 1 ) a commutative nonassociative algebra A α whose codimension sequence c n ( A α ) , n = 1 , 2 , … , is polynomially bounded and lim log n c n ( A α ) = 3 + α . As an application we are able to construct a new example of a variety with an infinite basis of identities.
Nonlinear embeddings: Applications to analysis, fractals and polynomial root finding
2016
We introduce $\mathcal{B}_{\kappa}$-embeddings, nonlinear mathematical structures that connect, through smooth paths parameterized by $\kappa$, a finite or denumerable set of objects at $\kappa=0$ (e.g. numbers, functions, vectors, coefficients of a generating function...) to their ordinary sum at $\kappa \to \infty$. We show that $\mathcal{B}_{\kappa}$-embeddings can be used to design nonlinear irreversible processes through this connection. A number of examples of increasing complexity are worked out to illustrate the possibilities uncovered by this concept. These include not only smooth functions but also fractals on the real line and on the complex plane. As an application, we use $\mat…
Polynomial identities on superalgebras: Classifying linear growth
2006
Abstract We classify, up to PI-equivalence, the superalgebras over a field of characteristic zero whose sequence of codimensions is linearly bounded. As a consequence we determine the linear functions describing the graded codimensions of a superalgebra.