Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA characterization of those automata that structurally generate finite groups
122
0
0.0
(
0
)
Added by
Ines Klimann
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Authors
Ines Klimann
Ask ChatGPT about the research
No Arabic abstract
Antonenko and Russyev independently have shown that any Mealy automaton with no cycles with exit--that is, where every cycle in the underlying directed graph is a sink component--generates a fi- nite (semi)group, regardless of the choice of the production functions. Antonenko has proved that this constitutes a characterization in the non-invertible case and asked for the invertible case, which is proved in this paper.
rate research
Read More
The simplest example of an infinite Burnside group arises in the class of automaton groups. However there is no known example of such a group generated by a reversible Mealy automaton. It has been proved that, for a connected automaton of size at most~3, or when the automaton is not bireversible, the generated group cannot be Burnside infinite. In this paper, we extend these results to automata with bigger stateset, proving that, if a connected reversible automaton has a prime number of states, it cannot generate an infinite Burnside group.
A register automaton is a finite automaton with finitely many registers ranging from an infinite alphabet. Since the valuations of registers are infinite, there are infinitely many configurations. We describe a technique to classify infinite register automata configurations into finitely many exact representative configurations. Using the finitary representation, we give an algorithm solving the reachability problem for register automata. We moreover define a computation tree logic for register automata and solve its model checking problem.
We characterize finite groups G generated by orthogonal transformations in a finite-dimensional Euclidean space V whose fixed point subspace has codimension one or two in terms of the corresponding quotient space V/G with its quotient piecewise linear structure.
We approach the task of computing a carefully synchronizing word of optimum length for a given partial deterministic automaton, encoding the problem as an instance of SAT and invoking a SAT solver. Our experiments demonstrate that this approach gives satisfactory results for automata with up to 100 states even if very modest computational resources are used. We compare our results with the ones obtained by the first author for exact synchronization, which is another version of synchronization studied in the literature, and draw some theoretical conclusions.
The potential of the exact quantum information processing is an interesting, important and intriguing issue. For examples, it has been believed that quantum tools can provide significant, that is larger than polynomial, advantages in the case of exact quantum computation only, or mainly, for problems with very special structures. We will show that this is not the case. In this paper the potential of quantum finite automata producing outcomes not only with a (high) probability, but with certainty (so called exactly) is explored in the context of their uses for solving promise problems and with respect to the size of automata. It is shown that for solving particular classes ${A^n}_{n=1}^{infty}$ of promise problems, even those without some very special structure, that succinctness of the exact quantum finite automata under consideration, with respect to the number of (basis) states, can be very small (and constant) though it grows proportional to $n$ in the case deterministic finite automata (DFAs) of the same power are used. This is here demonstrated also for the case that the component languages of the promise problems solvable by DFAs are non-regular. The method used can be applied in finding more exact quantum finite automata or quantum algorithms for other promise problems.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
