Search results for "automata"
showing 10 items of 453 documents
Codification schemes and finite automata
2000
This paper is a note on how Information Theory and Codification Theory are helpful in the computational design both of communication protocols and strategy sets in the framework of finitely repeated games played by boundedly rational agents. More precisely, we show the usefulness of both theories to improve the existing automata bounds of Neyman¿s (1998) work on finitely repeated games played by finite automata.
Linear-size suffix tries
2016
Suffix trees are highly regarded data structures for text indexing and string algorithms [MCreight 76, Weiner 73]. For any given string w of length n = | w | , a suffix tree for w takes O ( n ) nodes and links. It is often presented as a compacted version of a suffix trie for w, where the latter is the trie (or digital search tree) built on the suffixes of w. Here the compaction process replaces each maximal chain of unary nodes with a single arc. For this, the suffix tree requires that the labels of its arcs are substrings encoded as pointers to w (or equivalent information). On the contrary, the arcs of the suffix trie are labeled by single symbols but there can be Θ ( n 2 ) nodes and lin…
Learning Automata-based Misinformation Mitigation via Hawkes Processes
2021
AbstractMitigating misinformation on social media is an unresolved challenge, particularly because of the complexity of information dissemination. To this end, Multivariate Hawkes Processes (MHP) have become a fundamental tool because they model social network dynamics, which facilitates execution and evaluation of mitigation policies. In this paper, we propose a novel light-weight intervention-based misinformation mitigation framework using decentralized Learning Automata (LA) to control the MHP. Each automaton is associated with a single user and learns to what degree that user should be involved in the mitigation strategy by interacting with a corresponding MHP, and performing a joint ra…
A Fast Algorithm Finding the Shortest Reset Words
2013
In this paper we present a new fast algorithm for finding minimal reset words for finite synchronizing automata, which is a problem appearing in many practical applications. The problem is known to be computationally hard, so our algorithm is exponential in the worst case, but it is faster than the algorithms used so far and it performs well on average. The main idea is to use a bidirectional BFS and radix (Patricia) tries to store and compare subsets. Also a number of heuristics are applied. We give both theoretical and practical arguments showing that the effective branching factor is considerably reduced. As a practical test we perform an experimental study of the length of the shortest …
Integer Weighted Regression Tsetlin Machines
2020
The Regression Tsetlin Machine (RTM) addresses the lack of interpretability impeding state-of-the-art nonlinear regression models. It does this by using conjunctive clauses in propositional logic to capture the underlying non-linear frequent patterns in the data. These, in turn, are combined into a continuous output through summation, akin to a linear regression function, however, with non-linear components and binary weights. However, the resolution of the RTM output is proportional to the number of clauses employed. This means that computation cost increases with resolution. To address this problem, we here introduce integer weighted RTM clauses. Our integer weighted clause is a compact r…
A Musical Pattern Discovery System Founded on a Modeling of Listening Strategies
2004
Music is a domain of expression that conveys a paramount degree of complexity. The musical surface, composed of a multitude of notes, results from the elaboration of numerous structures of different types and sizes. The composer constructs this structural complexity in a more or less explicit way. The listener, faced by such a complex phenomenon, is able to reconstruct only a limited part of it, mostly in a non-explicit way. One particular aim of music analysis is to objectify such complexity, thus offering to the listener a tool for enriching the appreciation of music (Lartillot and SaintJames, 2004). The trouble is, traditional musical analysis, although offering a valuable understanding …
Reduction of the number of spectral bands in Landsat images: a comparison of linear and nonlinear methods
2006
We describe some applications of linear and nonlinear pro- jection methods in order to reduce the number of spectral bands in Land- sat multispectral images. The nonlinear method is curvilinear component analysis CCA, and we propose an adapted optimization of it for image processing, based on the use of principal-component analysis PCA, a linear method. The principle of CCA consists in reproducing the topol- ogy of the original space projection points in a reduced subspace, keep- ing the maximum of information. Our conclusions are: CCA is an im- provement for dimension reduction of multispectral images; CCA is really a nonlinear extension of PCA; CCA optimization through PCA called CCAinitP…
An efficient swap algorithm for the lattice Boltzmann method
2007
During the last decade, the lattice-Boltzmann method (LBM) as a valuable tool in computational fluid dynamics has been increasingly acknowledged. The widespread application of LBM is partly due to the simplicity of its coding. The most well-known algorithms for the implementation of the standard lattice-Boltzmann equation (LBE) are the two-lattice and two-step algorithms. However, implementations of the two-lattice or the two-step algorithm suffer from high memory consumption or poor computational performance, respectively. Ultimately, the computing resources available decide which of the two disadvantages is more critical. Here we introduce a new algorithm, called the swap algorithm, for t…
Modeling a teacher in a tutorial-like system using Learning Automata
2012
Published version of a chapter in the book: Transactions on Computational Collective Intelligence VIII. Also available from the publisher at: http://dx.doi.org/10.1007/978-3-642-34645-3_2 The goal of this paper is to present a novel approach to model the behavior of a Teacher in a Tutorial- like system. In this model, the Teacher is capable of presenting teaching material from a Socratic-type Domain model via multiple-choice questions. Since this knowledge is stored in the Domain model in chapters with different levels of complexity, the Teacher is able to present learning material of varying degrees of difficulty to the Students. In our model, we propose that the Teacher will be able to as…
Parallelization of Cellular Automata for Surface Reactions
2002
We present a parallel implementation of cellular automata to simulate chemical reactions on surfaces. The scaling of the computer time with the number of processors for this parallel implementation is quite close to the ideal T/P, where T is the computer time used for one single processor and P the number of processors. Two examples are presented to test the algorithm, the simple A+B->0 model and a realistic model for CO oxidation on Pt(110). By using large parallel simulations, it is possible to derive scaling laws which allow us to extrapolate to even larger system sizes and faster diffusion coefficients allowing us to make direct comparisons with experiments.