Search results for "Automaton"
showing 10 items of 257 documents
Arithmetical Analysis of Biomolecular Finite Automaton
2013
In the paper we present a theoretical analysis of extension of the finite automaton built on DNA (introduced by the Shapiro team) to an arbitrary number of states and symbols. In the implementation we use a new idea of several restriction enzymes instead of one. We give arithmetical conditions for the existence of such extensions in terms of ingredients used in the implementation.
Nonstochastic languages as projections of 2-tape quasideterministic languages
1998
A language L (n) of n-tuples of words which is recognized by a n-tape rational finite-probabilistic automaton with probability 1-e, for arbitrary e > 0, is called quasideterministic. It is proved in [Fr 81], that each rational stochastic language is a projection of a quasideterministic language L (n) of n-tuples of words. Had projections of quasideterministic languages on one tape always been rational stochastic languages, we would have a good characterization of the class of the rational stochastic languages. However we prove the opposite in this paper. A two-tape quasideterministic language exists, the projection of which on the first tape is a nonstochastic language.
Some considerations on Hydra groups and a new bound for the length of words
2014
Abstract After a survey on some recent results of Riley and others on Ackermann functions and Hydra groups, we make an analogy between DNA sequences, whose growth is the same of that of Hydra groups, and a musical piece, written with the same algorithmic criterion. This is mainly an aesthetic observation, which emphasizes the importance of the combinatorics of words in two different contexts. A result of specific mathematical interest is placed at the end, where we sharpen some previous bounds on deterministic finite automata in which there are languages with hairpins.
Multi-letter reversible and quantum finite automata
2007
The regular language (a+b)*a (the words in alphabet {a, b} having a as the last letter) is at the moment a classical example of a language not recognizable by a one-way quantum finite automaton (QFA). Up to now, there have been introduced many different models of QFAs, with increasing capabilities, but none of them can cope with this language. We introduce a new, quite simple modification of the QFA model (actually even a deterministic reversible FA model) which is able to recognize this language. We also completely characterise the set of languages recognizable by the new model FAs, by finding a "forbidden construction" whose presence or absence in the minimal deterministic (not necessaril…
Algebraic Results on Quantum Automata
2004
We use tools from the algebraic theory of automata to investigate the class of languages recognized by two models of Quantum Finite Automata (QFA): Brodsky and Pippenger’s end-decisive model, and a new QFA model whose definition is motivated by implementations of quantum computers using nucleo-magnetic resonance (NMR). In particular, we are interested in the new model since nucleo-magnetic resonance was used to construct the most powerful physical quantum machine to date. We give a complete characterization of the languages recognized by the new model and by Boolean combinations of the Brodsky-Pippenger model. Our results show a striking similarity in the class of languages recognized by th…
The Bayesian Learning Automaton — Empirical Evaluation with Two-Armed Bernoulli Bandit Problems
2009
The two-armed Bernoulli bandit (TABB) problem is a classical optimization problem where an agent sequentially pulls one of two arms attached to a gambling machine, with each pull resulting either in a reward or a penalty. The reward probabilities of each arm are unknown, and thus one must balance between exploiting existing knowledge about the arms, and obtaining new information.
Solving two‐armed Bernoulli bandit problems using a Bayesian learning automaton
2010
PurposeThe two‐armed Bernoulli bandit (TABB) problem is a classical optimization problem where an agent sequentially pulls one of two arms attached to a gambling machine, with each pull resulting either in a reward or a penalty. The reward probabilities of each arm are unknown, and thus one must balance between exploiting existing knowledge about the arms, and obtaining new information. The purpose of this paper is to report research into a completely new family of solution schemes for the TABB problem: the Bayesian learning automaton (BLA) family.Design/methodology/approachAlthough computationally intractable in many cases, Bayesian methods provide a standard for optimal decision making. B…
Research of Complex Forms in Cellular Automata by Evolutionary Algorithms
2004
This paper presents an evolutionary approach for the search for new complex cellular automata. Two evolutionary algorithms are used: the first one discovers rules supporting gliders and periodic patterns, and the second one discovers glider guns in cellular automata. An automaton allowing us to simulate AND and NOT gates is discovered. The results are a step toward the general simulation of Boolean circuits by this automaton and show that the evolutionary approach is a promising technic for searching for cellular automata that support universal computation.
A New Universal Cellular Automaton Discovered by Evolutionary Algorithms
2004
In Twenty Problems in the Theory of Cellular Automata, Stephen Wolfram asks “how common computational universality and undecidability [are] in cellular automata.” This papers provides elements of answer, as it describes how another universal cellular automaton than the Game of Life (Life) was sought and found using evolutionary algorithms. This paper includes a demonstration that consists in showing that the presented R automaton can both implement any logic circuit (logic universality) and a simulation of Life (universality in the Turing sense).