Search results for "AUTOMATA"
showing 10 items of 453 documents
Digital calculus: Cellular automata dynamics in closed form
2015
A simple mathematical expression for the universal map for cellular automata is found in closed form with the help of a digit function, whose most basic properties are established. This result is found after proving a theorem on the composition of functions on finite sets. The expression (and the technique used to obtain it) opens the possibility of gaining mathematical insight in any cellular automaton rule since it constitutes at the same time a simple and fast algorithm to implement any such rule.
Query automata
1999
A main task in document transformation and information retrieval is locating subtrees satisfying some pattern. Therefore, unary queries, i.e., queries that map a tree to a set of its nodes, play an important role in the context of structured document databases. We want to understand how the natural and well-studied computation model of tree automata can be used to compute such queries. We define a query automaton (QA) as a deterministic two-way finite automaton over trees that has the ability to select nodes depending on the state and the label at those nodes. We study QAs over ranked as well as over unranked trees. Unranked trees differ from ranked ones in that there is no bound on the num…
Negative results in the theory of games with lexicographic utilities
2003
When players may have lexicographic utilities, there are: (i) extensive games having a non-empty set of equilibria but empty sets of sequentially rational, sequential and perfect equilibria (ii) normal form games having a non-empty set of equilibria but an empty set of proper equilibria and no stable set of equilibria and (iii) two extensive games having the same normal form representation and disjoint sets of sequential equilibria.
Some decisional problems on rational relations
1997
Abstract In this paper we prove that the problem of deciding whether a deterministic rational relation is star-free is recursively solvable, although the same problem for any rational relation is undecidable. We also prove that a rational relation is star-free if and only if it is aperiodic and deterministic.
Bounded Computational Capacity Equilibrium
2010
We study repeated games played by players with bounded computational power, where, in contrast to Abreu and Rubisntein (1988), the memory is costly. We prove a folk theorem: the limit set of equilibrium payoffs in mixed strategies, as the cost of memory goes to 0, includes the set of feasible and individually rational payoffs. This result stands in sharp contrast to Abreu and Rubisntein (1988), who proved that when memory is free, the set of equilibrium payoffs in repeated games played by players with bounded computational power is a strict subset of the set of feasible and individually rational payoffs. Our result emphasizes the role of memory cost and of mixing when players have bounded c…
Learning Automaton Based On-Line Discovery and Tracking of Spatio-temporal Event Patterns
2010
Published version of an article from the book: Lecture Notes in Computer Science, 2010, Volume 6230/2010, 327-338. The original publication is available at Springerlink. http://dx.doi.org/10.1007/978-3-642-15246-7_31 Discovering and tracking of spatio-temporal patterns in noisy sequences of events is a difficult task that has become increasingly pertinent due to recent advances in ubiquitous computing, such as community-based social networking applications. The core activities for applications of this class include the sharing and notification of events, and the importance and usefulness of these functionalites increases as event-sharing expands into larger areas of one’s life. Ironically, …
The Average State Complexity of the Star of a Finite Set of Words Is Linear
2008
We prove that, for the uniform distribution over all sets Xof m(that is a fixed integer) non-empty words whose sum of lengths is n, $\mathcal{D}_X$, one of the usual deterministic automata recognizing X*, has on average $\mathcal{O}(n)$ states and that the average state complexity of X*is i¾?(n). We also show that the average time complexity of the computation of the automaton $\mathcal{D}_X$ is $\mathcal{O}(n\log n)$, when the alphabet is of size at least three.
On solving single elevator-like problems using a learning automata-based paradigm
2020
This paper concentrates on a host of problems with characteristics similar to those that are related to moving elevators within a building. These are referred to as Elevator-like problems (ELPs), and their common phenomena will be expanded on in the body of the paper. We shall resolve ELPs using a subfield of AI, namely the field of learning automata (LA). Rather than working with the well-established mathematical formulations of the field, our intention is to use these tools to tackle ELPs, and in particular, those that deal with single “elevators” moving between “floors”. ELPs have not been tackled before using AI. In a simplified domain, the ELP involves the problem of optimizing the sch…
Topological properties of cellular automata on trees
2012
We prove that there do not exist positively expansive cellular automata defined on the full k-ary tree shift (for k>=2). Moreover, we investigate some topological properties of these automata and their relationships, namely permutivity, surjectivity, preinjectivity, right-closingness and openness.
OntoVersionGraph : a change management methodology dedicated to formal ontologies and their user views in a collaborative context
2014
The world changes over time, impacting the knowledge of every subdomain it contains. Therefore systems describing the knowledge of a certain domain should be able to consider changes occurred to keep its knowledge representation up-to-date. Formal ontologies are one of them: they explicitly and formally represent the knowledge of a domain in all its forms and modes of existence. Collaboratively developed, a formal ontology allows the domain users to understand each other by sharing the same terminology despite the different assumptions they have on the domain conceptualization. However, due to its completeness, the complexity of its conceptualization can sometimes make the domain knowledge …