Search results for "COMPLEXITY"
showing 10 items of 1094 documents
Algorithmics for the Life Sciences
2013
The life sciences, in particular molecular biology and medicine, have wit- nessed fundamental progress since the discovery of the “the Double Helix”. A rele- vant part of such an incredible advancement in knowledge has been possible thanks to synergies with the mathematical sciences, on the one hand, and computer science, on the other. Here we review some of the most relevant aspects of this cooperation focusing on contributions given by the design, analysis and engineering of fast al- gorithms for the life sciences.
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…
Descriptional and Computational Complexity of the Circuit Representation of Finite Automata
2018
In this paper we continue to investigate the complexity of the circuit representation of DFA—BC-complexity. We compare it with nondeterministic state complexity, obtain upper and lower bounds which differ only by a factor of 4 for a Binary input alphabet. Also we prove that many simple operations (determining if a state is reachable or if an automaton is minimal) are PSPACE-complete for DFA given in circuit representation.
Multiple Usage of Random Bits in Finite Automata
2012
Finite automata with random bits written on a separate 2-way readable tape can recognize languages not recognizable by probabilistic finite automata. This shows that repeated reading of random bits by finite automata can have big advantages over one-time reading of random bits.
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.
The computational power of continuous time neural networks
1997
We investigate the computational power of continuous-time neural networks with Hopfield-type units. We prove that polynomial-size networks with saturated-linear response functions are at least as powerful as polynomially space-bounded Turing machines.
Some Afterthoughts on Hopfield Networks
1999
In the present paper we investigate four relatively independent issues, which complete our knowledge regarding the computational aspects of popular Hopfield nets. In Section 2 of the paper, the computational equivalence of convergent asymmetric and Hopfield nets is shown with respect to network size. In Section 3, the convergence time of Hopfield nets is analyzed in terms of bit representations. In Section 4, a polynomial time approximate algorithm for the minimum energy problem is shown. In Section 5, the Turing universality of analog Hopfield nets is studied. peerReviewed
Transition Function Complexity of Finite Automata
2019
State complexity of finite automata in some cases gives the same complexity value for automata which intuitively seem to have completely different complexities. In this paper we consider a new measure of descriptional complexity of finite automata -- BC-complexity. Comparison of it with the state complexity is carried out here as well as some interesting minimization properties are discussed. It is shown that minimization of the number of states can lead to a superpolynomial increase of BC-complexity.
FINITE AUTOMATA WITH ADVICE TAPES
2014
We define a model of advised computation by finite automata where the advice is provided on a separate tape. We consider several variants of the model where the advice is deterministic or randomized, the input tape head is allowed real-time, one-way, or two-way access, and the automaton is classical or quantum. We prove several separation results among these variants, demonstrate an infinite hierarchy of language classes recognized by automata with increasing advice lengths, and establish the relationships between this and the previously studied ways of providing advice to finite automata.
Finite Automata with Advice Tapes
2013
We define a model of advised computation by finite automata where the advice is provided on a separate tape. We consider several variants of the model where the advice is deterministic or randomized, the input tape head is allowed real-time, one-way, or two-way access, and the automaton is classical or quantum. We prove several separation results among these variants, and establish the relationships between this model and the previously studied ways of providing advice to finite automata.