Search results for "Lattice gas"
showing 10 items of 82 documents
Interactive Terrain Simulation and Force Distribution Models in Sand Piles
2006
This paper presents an application of Cellular Automata in the field of dry Granular Systems modelling While the study of granular systems is not a recent field, no efficient models exist, from a computational point of view, in classical methodologies Some previous works showed that the use of Cellular Automata is suitable for the development of models that can be used in real time applications This paper extends the existing Cellular Automata models in order to make them interactive A model for the reaction to external forces and a pressure distribution model are presented and analyzed, with numerical examples and simulations.
Capabilities of Ultrametric Automata with One, Two, and Three States
2016
Ultrametric automata use p-adic numbers to describe the random branching of the process of computation. Previous research has shown that ultrametric automata can have a significant decrease in computing complexity. In this paper we consider the languages that can be recognized by one-way ultrametric automata with one, two, and three states. We also show an example of a promise problem that can be solved by ultrametric integral automaton with three states.
On the Hierarchy Classes of Finite Ultrametric Automata
2015
This paper explores the language classes that arise with respect to the head count of a finite ultrametric automaton. First we prove that in the one-way setting there is a language that can be recognized by a one-head ultrametric finite automaton and cannot be recognized by any k-head non-deterministic finite automaton. Then we prove that in the two-way setting the class of languages recognized by ultrametric finite k-head automata is a proper subclass of the class of languages recognized by (k + 1)-head automata. Ultrametric finite automata are similar to probabilistic and quantum automata and have only just recently been introduced by Freivalds. We introduce ultrametric Turing machines an…
Combinatorics of Finite Words and Suffix Automata
2009
The suffix automaton of a finite word is the minimal deterministic automaton accepting the language of its suffixes. The states of the suffix automaton are the classes of an equivalence relation defined on the set of factors. We explore the relationship between the combinatorial properties of a finite word and the structural properties of its suffix automaton. We give formulas for expressing the total number of states and the total number of edges of the suffix automaton in terms of special factors of the word.
Regular Varieties of Automata and Coequations
2015
In this paper we use a duality result between equations and coequations for automata, proved by Ballester-Bolinches, Cosme-Ll´opez, and Rutten to characterize nonempty classes of deterministic automata that are closed under products, subautomata, homomorphic images, and sums. One characterization is as classes of automata defined by regular equations and the second one is as classes of automata satisfying sets of coequations called varieties of languages. We show how our results are related to Birkhoff’s theorem for regular varieties.
Deterministic generalized automata
1995
A generalized automaton (GA) is a finite automaton where the single transitions are defined on words rather than on single letters. Generalized automata were considered by K. Hashiguchi who proved that the problem of calculating the size of a minimal GA is decidable.
The Complexity of Probabilistic versus Quantum Finite Automata
2002
We present a language Ln which is recognizable by a probabilistic finite automaton (PFA) with probability 1 - ? for all ? > 0 with O(log2 n) states, with a deterministic finite automaton (DFA) with O(n) states, but a quantum finite automaton (QFA) needs at least 2?(n/log n) states.
Non-constructive Methods for Finite Probabilistic Automata
2007
Size (the number of states) of finite probabilistic automata with an isolated cut-point can be exponentially smaller than the size of any equivalent finite deterministic automaton. The result is presented in two versions. The first version depends on Artin's Conjecture (1927) in Number Theory. The second version does not depend on conjectures but the numerical estimates are worse. In both versions the method of the proof does not allow an explicit description of the languages used. Since our finite probabilistic automata are reversible, these results imply a similar result for quantum finite automata.
Counting with Probabilistic and Ultrametric Finite Automata
2014
We investigate the state complexity of probabilistic and ultrametric finite automata for the problem of counting, i.e. recognizing the one-word unary language \(C_n=\left\{ 1^n \right\} \). We also review the known results for other types of automata.
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 …