Search results for "formal"
showing 10 items of 1654 documents
Quantum Finite Multitape Automata
1999
Quantum finite automata were introduced by C. Moore, J. P. Crutchfield [4], and by A. Kondacs and J. Watrous [3]. This notion is not a generalization of the deterministic finite automata. Moreover, in [3] it was proved that not all regular languages can be recognized by quantum finite automata. A. Ambainis and R. Freivalds [1] proved that for some languages quantum finite automata may be exponentially more concise rather than both deterministic and probabilistic finite automata. In this paper we introduce the notion of quantum finite multitape automata and prove that there is a language recognized by a quantum finite automaton but not by deterministic or probabilistic finite automata. This …
Probabilistic Reversible Automata and Quantum Automata
2002
To study relationship between quantum finite automata and probabilistic finite automata, we introduce a notion of probabilistic reversible automata (PRA, or doubly stochastic automata). We find that there is a strong relationship between different possible models of PRA and corresponding models of quantum finite automata. We also propose a classification of reversible finite 1-way automata.
Implications of quantum automata for contextuality
2014
We construct zero error quantum finite automata (QFAs) for promise problems which cannot be solved by bounded error probabilistic finite automata (PFAs). Here is a summary of our results: There is a promise problem solvable by an exact two way QFA in exponential expected time but not by any bounded error sublogarithmic space probabilistic Turing machine (PTM). There is a promise problem solvable by an exact two way QFA in quadratic expected time but not by any bounded error o(loglogn) space PTMs in polynomial expected time. The same problem can be solvable by a one way Las Vegas (or exact two way) QFA with quantum head in linear (expected) time. There is a promise problem solvable by a Las …
Marked systems and circular splicing
2007
Splicing systems are generative devices of formal languages, introduced by Head in 1987 to model biological phenomena on linear and circular DNA molecules. In this paper we introduce a special class of finite circular splicing systems named marked systems. We prove that a marked system S generates a regular circular language if and only if S satisfies a special (decidable) property. As a consequence, we show that we can decide whether a regular circular language is generated by a marked system and we characterize the structure of these regular circular languages.
Indecomposable modules over the Virasoro Lie algebra and a conjecture of V. Kac
1991
We consider a class of indecomposable modules over the Virasoro Lie algebra that we call bounded admissible modules. We get results concerning the center and the dimensions of the weight spaces. We prove that these modules always contain a submodule with one-dimensional weight spaces. From this follows the proof of a conjecture of V. Kac concerning the classification of simple admissible modules.
Non-integrality of the PI-exponent of special Lie algebras
2013
If L is a special Lie algebra over a field of characteristic zero, its sequence of codimensions is exponentially bounded. The PI-exponent measures the exponential rate of growth of such sequence and here we give a first example of a special Lie algebra whose (upper and lower) PI-exponent is non-integer.
On the Codimension Growth of Finite-Dimensional Lie Algebras
1999
Abstract We study the exponential growth of the codimensions cn(L) of a finite-dimensional Lie algebra L over a field of characteristic zero. We show that if the solvable radical of L is nilpotent then lim n → ∞ c n ( L ) exists and is an integer.
LEFT INVARIANT COMPLEX STRUCTURES ON NILPOTENT SIMPLY CONNECTED INDECOMPOSABLE 6-DIMENSIONAL REAL LIE GROUPS
2007
Integrable complex structures on indecomposable 6-dimensional nilpotent real Lie algebras have been computed in a previous paper, along with normal forms for representatives of the various equivalence classes under the action of the automorphism group. Here we go to the connected simply connected Lie group G0 associated to such a Lie algebra 𝔤. For each normal form J of integrable complex structures on 𝔤, we consider the left invariant complex manifold G = (G0, J) associated to G0 and J. We explicitly compute a global holomorphic chart for G and we write down the multiplication in that chart.
Some criteria for detecting capable Lie algebras
2013
Abstract In virtue of a recent bound obtained in [P. Niroomand, F.G. Russo, A note on the Schur multiplier of a nilpotent Lie algebra, Comm. Algebra 39 (2011) 1293–1297], we classify all capable nilpotent Lie algebras of finite dimension possessing a derived subalgebra of dimension one. Indirectly, we find also a criterion for detecting noncapable Lie algebras. The final part contains a construction, which shows that there exist capable Lie algebras of arbitrary big corank (in the sense of Berkovich–Zhou).
A restriction on the schur multiplier of nilpotent lie algebras
2011
An improvement of a bound of Yankosky (2003) is presented in this paper, thanks to a restriction which has been recently obtained by the authors on the Schur multiplier M(L) of a finite dimensional nilpotent Lie algebra L. It is also described the structure of all nilpotent Lie algebras such that the bound is attained. An important role is played by the presence of a derived subalgebra of maximal dimension. This allows precision on the size of M(L). Among other results, applications to the non-abelian tensor square L ⊗ L are illustrated.