Search results for "Affine"

Simple and semisimple Lie algebras and codimension growth

1999

On 2-(n^2,2n,2n-1) designs with three intersection numbers

2007

The simple incidence structure $${\mathcal{D}(\mathcal{A},2)}$$ , formed by the points and the unordered pairs of distinct parallel lines of a finite affine plane $${\mathcal{A}=(\mathcal{P}, \mathcal{L})}$$ of order n > 4, is a 2 --- (n 2,2n,2n---1) design with intersection numbers 0,4,n. In this paper, we show that the converse is true, when n ? 5 is an odd integer.

Dimensions of random affine code tree fractals

2014

We calculate the almost sure Hausdorff dimension for a general class of random affine planar code tree fractals. The set of probability measures describing the randomness includes natural measures in random $V$-variable and homogeneous Markov constructions.

Approximate convex hull of affine iterated function system attractors

2012

International audience; In this paper, we present an algorithm to construct an approximate convex hull of the attractors of an affine iterated function system (IFS). We construct a sequence of convex hull approximations for any required precision using the self-similarity property of the attractor in order to optimize calculations. Due to the affine properties of IFS transformations, the number of points considered in the construction is reduced. The time complexity of our algorithm is a linear function of the number of iterations and the number of points in the output convex hull. The number of iterations and the execution time increases logarithmically with increasing accuracy. In additio…

On the computational power of affine automata

2017

We investigate the computational power of affine automata (AfAs) introduced in [4]. In particular, we present a simpler proof for how to change the cutpoint for any affine language and a method how to reduce error in bounded error case. Moreover, we address to the question of [4] by showing that any affine language can be recognized by an AfA with certain limitation on the entries of affine states and transition matrices. Lastly, we present the first languages shown to be not recognized by AfAs with bounded-error.

On a Conjecture by Christian Choffrut

2017

It is one of the most famous open problems to determine the minimum amount of states required by a deterministic finite automaton to distinguish a pair of strings, which was stated by Christian Choffrut more than thirty years ago. We investigate the same question for different automata models and we obtain new upper and lower bounds for some of them including alternating, ultrametric, quantum, and affine finite automata.

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.

Finite linear spaces in which any n-gon is euclidean

1986

Abstract An n-gon of a linear space is a set S of n points no three of which are collinear. By a diagonal point of S we mean a point p off S with the property that at least two lines through p intersect S in two points. The number of diagonal points is called the type of S. For example, a 4-gon has at most three diagonal points. We call an n-gon euclidean if (roughly speaking) it contains the maximal possible number of 4-gons of type 3. In this paper, we characterize all finite linear spaces in which, for a fixed number n ⩾ 5, any n-gon is euclidean. It turns out that these structures are essentially projective spaces or punctured projective spaces.

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 …