Search results for "Automata"
showing 10 items of 453 documents
Learning Automata Based Q-learning for Content Placement in Cooperative Caching
2019
An optimization problem of content placement in cooperative caching is formulated, with the aim of maximizing sum mean opinion score (MOS) of mobile users. Firstly, a supervised feed-forward back-propagation connectionist model based neural network (SFBC-NN) is invoked for user mobility and content popularity prediction. More particularly, practical data collected from GPS-tracker app on smartphones is tackled to test the accuracy of mobility prediction. Then, a learning automata-based Q-learning (LAQL) algorithm for cooperative caching is proposed, in which learning automata (LA) is invoked for Q-learning to obtain an optimal action selection in a random and stationary environment. It is p…
Quantum counter automata
2011
The question of whether quantum real-time one-counter automata (rtQ1CAs) can outperform their probabilistic counterparts has been open for more than a decade. We provide an affirmative answer to this question, by demonstrating a non-context-free language that can be recognized with perfect soundness by a rtQ1CA. This is the first demonstration of the superiority of a quantum model to the corresponding classical one in the real-time case with an error bound less than 1. We also introduce a generalization of the rtQ1CA, the quantum one-way one-counter automaton (1Q1CA), and show that they too are superior to the corresponding family of probabilistic machines. For this purpose, we provide gene…
Special factors and the combinatorics of suffix and factor automata
2011
AbstractThe suffix automaton (resp. factor automaton) of a finite word w is the minimal deterministic automaton recognizing the set of suffixes (resp. factors) of w. We study the relationships between the structure of the suffix and factor automata and classical combinatorial parameters related to the special factors of w. We derive formulae for the number of states of these automata. We also characterize the languages LSA and LFA of words having respectively suffix automaton and factor automaton with the minimal possible number of states.
Unary Probabilistic and Quantum Automata on Promise Problems
2015
We continue the systematic investigation of probabilistic and quantum finite automata (PFAs and QFAs) on promise problems by focusing on unary languages. We show that bounded-error QFAs are more powerful than PFAs. But, in contrary to the binary problems, the computational powers of Las-Vegas QFAs and bounded-error PFAs are equivalent to deterministic finite automata (DFAs). Lastly, we present a new family of unary promise problems with two parameters such that when fixing one parameter QFAs can be exponentially more succinct than PFAs and when fixing the other parameter PFAs can be exponentially more succinct than DFAs.
From deterministic cellular automata to coupled map lattices
2016
A general mathematical method is presented for the systematic construction of coupled map lattices (CMLs) out of deterministic cellular automata (CAs). The entire CA rule space is addressed by means of a universal map for CAs that we have recently derived and that is not dependent on any freely adjustable parameters. The CMLs thus constructed are termed real-valued deterministic cellular automata (RDCA) and encompass all deterministic CAs in rule space in the asymptotic limit $\kappa \to 0$ of a continuous parameter $\kappa$. Thus, RDCAs generalize CAs in such a way that they constitute CMLs when $\kappa$ is finite and nonvanishing. In the limit $\kappa \to \infty$ all RDCAs are shown to ex…
Achieving Unbounded Resolution inFinitePlayer Goore Games Using Stochastic Automata, and Its Applications
2012
Abstract This article concerns the sequential solution to a distributed stochastic optimization problem using learning automata and the Goore game (also referred to as the Gur game in the related literature). The amazing thing about our solution is that, unlike traditional methods, which need N automata (where N determines the degree of accuracy), in this article, we show that we can obtain arbitrary accuracy by recursively using only three automata. To be more specific, the Goore game (GG) introduced in Tsetlin (1973) has the fascinating property that it can be resolved in a completely distributed manner with no inter-communication between the players. The game has recently found applicati…
Adaptive sparse representation of continuous input for tsetlin machines based on stochastic searching on the line
2021
This paper introduces a novel approach to representing continuous inputs in Tsetlin Machines (TMs). Instead of using one Tsetlin Automaton (TA) for every unique threshold found when Booleanizing continuous input, we employ two Stochastic Searching on the Line (SSL) automata to learn discriminative lower and upper bounds. The two resulting Boolean features are adapted to the rest of the clause by equipping each clause with its own team of SSLs, which update the bounds during the learning process. Two standard TAs finally decide whether to include the resulting features as part of the clause. In this way, only four automata altogether represent one continuous feature (instead of potentially h…
On modal mu-calculus over finite graphs with bounded strongly connected components.
2010
For every positive integer k we consider the class SCCk of all finite graphs whose strongly connected components have size at most k. We show that for every k, the Modal mu-Calculus fixpoint hierarchy on SCCk collapses to the level Delta2, but not to Comp(Sigma1,Pi1) (compositions of formulas of level Sigma1 and Pi1). This contrasts with the class of all graphs, where Delta2=Comp(Sigma1,Pi1).
A solution to the stochastic point location problem in metalevel nonstationary environments.
2008
This paper reports the first known solution to the stochastic point location (SPL) problem when the environment is nonstationary. The SPL problem involves a general learning problem in which the learning mechanism (which could be a robot, a learning automaton, or, in general, an algorithm) attempts to learn a "parameter," for example, lambda*, within a closed interval. However, unlike the earlier reported results, we consider the scenario when the learning is to be done in a nonstationary setting. For each guess, the environment essentially informs the mechanism, possibly erroneously (i.e., with probability p), which way it should move to reach the unknown point. Unlike the results availabl…
Modelling and simulation of several interacting cellular automata
2015
Cellular automata are used for modelling and simulation of many systems. In some applications, the system is formed by a set of subsystems that can be modelled separately, but, in such cases, the existence of interactions between these subsystems requires additional modelling and computer programming. In this paper we propose a modelling methodology for the simulation of a set of cellular automata models that interact with each other. The modelling methodology is described, together with an insight on implementation details. Also, it is applied to a particular cellular automata model, the Sanpile model, to illustrate its use and to obtain some example simulations.