Search results for "transformation"
showing 10 items of 1634 documents
Affine Automata Verifiers
2021
We initiate the study of the verification power of Affine finite automata (AfA) as a part of Arthur-Merlin (AM) proof systems. We show that every unary language is verified by a real-valued AfA verifier. Then, we focus on the verifiers restricted to have only integer-valued or rational-valued transitions. We observe that rational-valued verifiers can be simulated by integer-valued verifiers, and their protocols can be simulated in nondeterministic polynomial time. We show that this upper bound is tight by presenting an AfA verifier for NP-complete problem SUBSETSUM. We also show that AfAs can verify certain non-affine and non-stochastic unary languages.
The support localization property of the strongly embedded subspaces of banach function spaces
2015
[EN] Motivated by the well known Kadec-Pelczynski disjointifcation theorem, we undertake an analysis of the supports of non-zero functions in strongly embedded subspaces of Banach functions spaces. The main aim is to isolate those properties that bring additional information on strongly embedded subspaces. This is the case of the support localization property, which is a necessary condition fulflled by all strongly embedded subspaces. Several examples that involve Rademacher functions, the Volterra operator, Lorentz spaces or Orlicz spaces are provided.
Equivariant Triviality of Quasi-Monomial Triangular $$\mathbb{G}_{a}$$-Actions on $$\mathbb{A}^{4}$$
2014
We give a direct and self-contained proof of the fact that additive group actions on affine four-space generated by certain types of triangular derivations are translations whenever they are proper. The argument, which is based on explicit techniques, provides an illustration of the difficulties encountered and an introduction to the more abstract methods which were used recently by the authors to solve the general triangular case.
Language Recognition Power and Succinctness of Affine Automata
2016
In this work we study a non-linear generalization based on affine transformations of probabilistic and quantum automata proposed recently by Diaz-Caro and Yakaryilmaz [6] referred as affine automata. First, we present efficient simulations of probabilistic and quantum automata by means of affine automata which allows us to characterize the class of exclusive stochastic languages. Then, we initiate a study on the succintness of affine automata. In particular, we show that an infinite family of unary regular languages can be recognized by 2-state affine automata, whereas the number of states of any quantum and probabilistic automata cannot be bounded. Finally, we present the characterization …
A Vector Approach to Euler's Line of a Triangle
1992
Among the many interesting properties that triangles possess there is one that quickly attracts our curiosity and stays easily in our mind: The centroid, circumcentre and orthocentre all lie in a common line (Euler's Line). An elementary simple proof can be obtained using metric and affine properties of the points involved, [1]. Our aim here is to illustrate a proof using vectors. We identify points in the plane with their position vectors. It is easy to see that the centroid G of the triangle ABC is given by the identity
A note on Sturmian words
2012
International audience; We describe an algorithm which, given a factor of a Sturmian word, computes the next factor of the same length in the lexicographic order in linear time. It is based on a combinatorial property of Sturmian words which is related with the Burrows-Wheeler transformation.
The Herzog-Vasconcelos conjecture for affine semigroup rings
1999
Let S be a simplicial affine semigroup such that its semigroup ring A = k[S] is Buchsbaum. We prove for such A the Herzog-Vasconcelos conjecture: If the A-module Der(k)A of k-linear derivations of A has finite projective dimension then it is free and hence A is a polynomial ring by the well known graded case of the Zariski-Lipman conjecture.
Error-Free Affine, Unitary, and Probabilistic OBDDs
2018
We introduce the affine OBDD model and show that zero-error affine OBDDs can be exponentially narrower than bounded-error unitary and probabilistic OBDDs on certain problems. Moreover, we show that Las Vegas unitary and probabilistic OBDDs can be quadratically narrower than deterministic OBDDs. We also obtain the same results for the automata versions of these models.
On n–Fold Blocking Sets
1986
An n-fold blocking set is a set of n-disjoint blocking sets. We shall prove upper and lower bounds for the number of components in an n-fold blocking set in projective and affine spaces.
Error-Free Affine, Unitary, and Probabilistic OBDDs
2021
We introduce the affine OBDD model and show that zero-error affine OBDDs can be exponentially narrower than bounded-error unitary and probabilistic OBDDs on certain problems. Moreover, we show that Las-Vegas unitary and probabilistic OBDDs can be quadratically narrower than deterministic OBDDs. We also obtain the same results for the automata counterparts of these models.