Search results for "Automata"

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.

From Nerode's congruence to Suffix Automata with mismatches

2009

AbstractIn this paper we focus on the minimal deterministic finite automaton Sk that recognizes the set of suffixes of a word w up to k errors. As first result we give a characterization of the Nerode’s right-invariant congruence that is associated with Sk. This result generalizes the classical characterization described in [A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. Chen, J. Seiferas, The smallest automaton recognizing the subwords of a text, Theoretical Computer Science, 40, 1985, 31–55]. As second result we present an algorithm that makes use of Sk to accept in an efficient way the language of all suffixes of w up to k errors in every window of size r of a text, where r is the…

Extending formal language hierarchies to higher dimensions

1999

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.

Connecting Granular and Topological Relations through Description Logics

2021

Granularity deals with organizing in greater or lesser detail data, information, and knowledge that resides at a granular level. This organization is carried out according to certain criteria, which thereby provide a context view or dimension also called granular perspective. Topological relations express spatial associations among geospatial features (points, polylines, and polygons); they represent a horizontal spatial analysis. The two domains allow scientists to conceive different perspectives of the world. In this article, we aim to combine the two representations through Description Logics (DL) rules to relate granular (vertical representation) and geospatial topological (horizontal r…

Motzkin subposets and Motzkin geodesics in Tamari lattices

2014

The Tamari lattice of order n can be defined by the set D n of Dyck words endowed with the partial order relation induced by the well-known rotation transformation. In this paper, we study this rotation on the restricted set of Motzkin words. An upper semimodular join semilattice is obtained and a shortest path metric can be defined. We compute the corresponding distance between two Motzkin words in this structure. This distance can also be interpreted as the length of a geodesic between these Motzkin words in a Tamari lattice. So, a new upper bound is obtained for the classical rotation distance between two Motzkin words in a Tamari lattice. For some specific pairs of Motzkin words, this b…

Achieving Intelligent Traffic-aware Consolidation of Virtual Machines in a Data Center Using Learning Automata

2016

Cloud Computing (CC) is becoming increasingly pertinent and popular. A natural consequence of this is that many modern-day data centers experience very high internal traffic within the data centers themselves. The VMs with high mutual traffic often end up being far apart in the data center network, forcing them to communicate over unnecessarily long distances. The consequent traffic bottlenecks negatively affect both the performance of the application and the network in its entirety, posing nontrivial challenges for the administrators of these cloudbased data centers. The problem can, quite naturally, be compartmentalized into two phases which follow each other. First of all, the VMs are co…

Identifying Unreliable Sensors Without a Knowledge of the Ground Truth in Deceptive Environments

2017

This paper deals with the extremely fascinating area of “fusing” the outputs of sensors without any knowledge of the ground truth. In an earlier paper, the present authors had recently pioneered a solution, by mapping it onto the fascinating paradox of trying to identify stochastic liars without any additional information about the truth. Even though that work was significant, it was constrained by the model in which we are living in a world where “the truth prevails over lying”. Couched in the terminology of Learning Automata (LA), this corresponds to the Environment (Since the Environment is treated as an entity in its own right, we choose to capitalize it, rather than refer to it as an “…

Languages associated with saturated formations of groups

2013

International audience; In a previous paper, the authors have shown that Eilenberg's variety theorem can be extended to more general structures, called formations. In this paper, we give a general method to describe the languages corresponding to saturated formations of groups, which are widely studied in group theory. We recover in this way a number of known results about the languages corresponding to the classes of nilpotent groups, soluble groups and supersoluble groups. Our method also applies to new examples, like the class of groups having a Sylow tower.; Dans un article précédent, les auteurs avaient montré comment étendre le théorème des variétés d'Eilenberg à des structures plus g…

From Arithmetic to Logic based AI: A Comparative Analysis of Neural Networks and Tsetlin Machine

2020

Neural networks constitute a well-established design method for current and future generations of artificial intelligence. They depends on regressed arithmetic between perceptrons organized in multiple layers to derive a set of weights that can be used for classification or prediction. Over the past few decades, significant progress has been made in low-complexity designs enabled by powerful hardware/software ecosystems. Built on the foundations of finite-state automata and game theory, Tsetlin Machine is increasingly gaining momentum as an emerging artificial intelligence design method. It is fundamentally based on propositional logic based formulation using booleanized input features. Rec…