Search results for "Cellular Automata"
showing 10 items of 113 documents
New Results on Vector and Homing Vector Automata
2019
We present several new results and connections between various extensions of finite automata through the study of vector automata and homing vector automata. We show that homing vector automata outperform extended finite automata when both are defined over $ 2 \times 2 $ integer matrices. We study the string separation problem for vector automata and demonstrate that generalized finite automata with rational entries can separate any pair of strings using only two states. Investigating stateless homing vector automata, we prove that a language is recognized by stateless blind deterministic real-time version of finite automata with multiplication iff it is commutative and its Parikh image is …
Classical automata on promise problems
2015
Promise problems were mainly studied in quantum automata theory. Here we focus on state complexity of classical automata for promise problems. First, it was known that there is a family of unary promise problems solvable by quantum automata by using a single qubit, but the number of states required by corresponding one-way deterministic automata cannot be bounded by a constant. For this family, we show that even two-way nondeterminism does not help to save a single state. By comparing this with the corresponding state complexity of alternating machines, we then get a tight exponential gap between two-way nondeterministic and one-way alternating automata solving unary promise problems. Secon…
Quantum finite multitape automata
1999
Quantum finite automata were introduced by C.Moore, J.P. Crutchfield, and by A.Kondacs and J.Watrous. This notion is not a generalization of the deterministic finite automata. Moreover, it was proved that not all regular languages can be recognized by quantum finite automata. A.Ambainis and R.Freivalds 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 a deterministic or probabilistic finite automata. This is the first result on …
The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpoints
2019
Discrete Mathematics & Theoretical Computer Science ; vol. 22 no. 1 ; Automata, Logic and Semantics ; 1365-8050
Exact affine counter automata
2017
We introduce an affine generalization of counter automata, and analyze their ability as well as affine finite automata. Our contributions are as follows. We show that there is a language that can be recognized by exact realtime affine counter automata but by neither 1-way deterministic pushdown automata nor realtime deterministic k-counter automata. We also show that a certain promise problem, which is conjectured not to be solved by two-way quantum finite automata in polynomial time, can be solved by Las Vegas affine finite automata. Lastly, we show that how a counter helps for affine finite automata by showing that the language MANYTWINS, which is conjectured not to be recognized by affin…
Finite automata with advice tapes
2013
We define a model of advised computation by finite automata where the advice is provided on a separate tape. We consider several variants of the model where the advice is deterministic or randomized, the input tape head is allowed real-time, one-way, or two-way access, and the automaton is classical or quantum. We prove several separation results among these variants, demonstrate an infinite hierarchy of language classes recognized by automata with increasing advice lengths, and establish the relationships between this and the previously studied ways of providing advice to finite automata.
The infinite dihedral group
2022
We describe the infinite dihedral group as automaton group. We collect basic results and give full proofs in details for all statements.
Implementing a Margolus Neighborhood Cellular Automata on a FPGA
2003
Margolus neighborhood is the easiest form of designing Cellular Automata Rules with features such as invertibility or particle conserving. In this paper we introduce a notation to describe completely a rule based on this neighborhood and implement it in two ways: The first corresponds to a classical RAM-based implementation, while the second, based on concurrent cells, is useful for smaller systems in which time is a critical parameter. This implementation has the feature that the evolution of all the cells in the design is performed in the same clock cycle.
Mathematical logic and quantum finite state automata
2009
AbstractThis paper is a review of the connection between formulas of logic and quantum finite-state automata in respect to the language recognition and acceptance probability of quantum finite-state automata. As is well known, logic has had a great impact on classical computation, it is promising to study the relation between quantum finite-state automata and mathematical logic. After a brief introduction to the connection between classical computation and logic, the required background of the logic and quantum finite-state automata is provided and the results of the connection between quantum finite-state automata and logic are presented.
Fuzzy Cognitive Maps-Based Modelling of Residential Mobility Dynamics: GeoComputation Approach
2017
International audience; This paper is concerned with proposing a fuzzy cognitive maps (FCMs) driven approach for geocomputing urban dynamics (social, spatial and temporal) as a complex system. After an overview of FCMs, mathematical fundamentals methodology that this theory suggests are examined. Then, the formalization and algorithm implementation of a model apply to residential mobility in urban space based on FCMs is described. Very good results were obtained, demonstrating that the use of these modelling approach is good and reliable.