Search results for "PROB"

Online Induction of Probabilistic Real Time Automata

2012

Probabilistic real time automata (PRTAs) are a representation of dynamic processes arising in the sciences and industry. Currently, the induction of automata is divided into two steps: the creation of the prefix tree acceptor (PTA) and the merge procedure based on clustering of the states. These two steps can be very time intensive when a PRTA is to be induced for massive or even unbounded data sets. The latter one can be efficiently processed, as there exist scalable online clustering algorithms. However, the creation of the PTA still can be very time consuming. To overcome this problem, we propose a genuine online PRTA induction approach that incorporates new instances by first collapsing…

A basic analysis toolkit for biological sequences

2007

This paper presents a software library, nicknamed BATS, for some basic sequence analysis tasks. Namely, local alignments, via approximate string matching, and global alignments, via longest common subsequence and alignments with affine and concave gap cost functions. Moreover, it also supports filtering operations to select strings from a set and establish their statistical significance, via z-score computation. None of the algorithms is new, but although they are generally regarded as fundamental for sequence analysis, they have not been implemented in a single and consistent software package, as we do here. Therefore, our main contribution is to fill this gap between algorithmic theory an…

Why a Quantum Tool in Classical Contexts?

2012

Oxygen isotope composition of North American bobcat (Lynx rufus) and puma (Puma concolor) bone phosphate: implications for provenance and climate rec…

2015

Feline carnivores are threatened by illegal wildlife trade. Tracing the provenance of unknown felid tissues via stable isotope analysis could provide important information in wildlife crime investigations. The oxygen isotope composition of mammalian skeletal phosphate (δ18Op) is widely applied to trace the origin of animal remains and to reconstruct migratory patterns in palaeontological, archaeological, ecological and wildlife forensic applications. Teeth and bones of terrestrial mammals form at constant body temperature in isotope equilibrium with body water, which is predominantly controlled by ingested meteoric water (δ18Ow) that varies systematically with latitude, altitude and climate…

Quantum versus Probabilistic One-Way Finite Automata with Counter

2001

The paper adds the one-counter one-way finite automaton [6] to the list of classical computing devices having quantum counterparts more powerful in some cases. Specifically, two languages are considered, the first is not recognizable by deterministic one-counter one-way finite automata, the second is not recognizable with bounded error by probabilistic one-counter one-way finite automata, but each recognizable with bounded error by a quantum one-counter one-way finite automaton. This result contrasts the case of one-way finite automata without counter, where it is known [5] that the quantum device is actually less powerful than its classical counterpart.

Tally languages accepted by Monte Carlo pushdown automata

1997

Rather often difficult (and sometimes even undecidable) problems become easily decidable for tally languages, i.e. for languages in a single-letter alphabet. For instance, the class of languages recognizable by 1-way nondeterministic pushdown automata equals the class of the context-free languages, but the class of the tally languages recognizable by 1-way nondeterministic pushdown automata, contains only regular languages [LP81]. We prove that languages over one-letter alphabet accepted by randomized one-way 1-tape Monte Carlo pushdown automata are regular. However Monte Carlo pushdown automata can be much more concise than deterministic 1-way finite state automata.

Ultrametric Finite Automata and Turing Machines

2013

We introduce a notion of ultrametric automata and Turing machines using p-adic numbers to describe random branching of the process of computation. These automata have properties similar to the properties of probabilistic automata but complexity of probabilistic automata and complexity of ultrametric automata can differ very much.

Ultrametric Algorithms and Automata

2015

We introduce a notion of ultrametric automata and Turing machines using p-adic numbers to describe random branching of the process of computation. These automata have properties similar to the properties of probabilistic automata but complexity of probabilistic automata and complexity of ultrametric automata can differ very much.

How to simulate free will in a computational device

1999

Since we believe that human brain is not a purely deterministic device merely reacting to the environment but rather it is capable to a free will, Theoretical Computer Science has also tried to develop a system of notions generalizing determinism. Nondeterministic and probabilistic algorithms were the first generalizations. Nondeterministic machines constitute an important part of the Theory of Computation. Nondeterminism is a useful way to describe possible choices. In real life there are many regulations restricting our behavior. These regulations nearly always leave some freedom for us how to react. Such regulations are best described in terms of nondeterministic algorithms. Nondetermini…

Quantum Real - Time Turing Machine

2001

The principles of quantum computation differ from the principles of classical computation very much. Quantum analogues to the basic constructions of the classical computation theory, such as Turing machine or finite 1-way and 2-ways automata, do not generalize deterministic ones. Their capabilities are incomparable. The aim of this paper is to introduce a quantum counterpart for real - time Turing machine. The recognition of a special kind of language, that can't be recognized by a deterministic real - time Turing machine, is shown.