CiteSeerX Scientific Literature Digital Library and Search Engine
(2,580,659 recursos)
CiteSeerX is a scientific literature digital library and search engine that focuses primarily on the literature in computer and information science. CiteSeerx aims to improve the dissemination of scientific literature and to provide improvements in functionality, usability, availability, cost, comprehensiveness, efficiency, and timeliness in the access of scientific and scholarly knowledge

Mostrando recursos 1 - 20 de 2,516,502

1.
Efficient algorithms for membership in Boolean hierarchies of regular languages - C. Glasser; H. Schmitz; V. Selivanov
The purpose of this paper is to provide efficient algorithms that decide membership for classes of several Boolean hierarchies for which efficiency (or even decidability) were previously not known. We develop new forbidden-chain characterizations for the single levels of these hierarchies and obtain the following results: • The classes of the Boolean hierarchy over level Σ1 of the dot-depth hierarchy are decidable in NL (previously only the decidability was known). The same remains true if predicates mod d for fixed d are allowed. • If modular predicates for arbitrary d are allowed, then the classes of the Boolean hierarchy over...

2.
On Self-Assembling Graphs in vitro - Max H. Garzon; Rusell J. Deaton; Ken Barnes; J. A. Rose
In this paper we identify a new type of structures that can be assembled in vitro by self-regulating molecular processes. This type of structure, the so-called automatic graphs, is a class of highly symmetric graphs Cayley graphs that have the same local appearance from every node and yet admit a finite-state navigator set that can discriminate global properties of the graph. We show how the navigator can be implemented as a molecule that directs the self-assembly process to build such graphs as nanostructures in DNA molecules. Cayley graphs form a class of highly regular structures that can, in principle, be...

3.
Thermodynamic Constraints on DNA-based Computing - R. Deaton; M. Garzon
Computing with biological macromolecules, such as DNA, is fundamentally a physical/chemical process. The DNA chemistry introduces a level of complexity that makes reliable, efficient, and scalable computations a challenge. All the chemical and thermodynamic factors have to be analyzed and controlled in order for the molecular algorithm to produce the intended result. For instance, a computation based on DNA requires that the problem instance be encoded in single strands of DNA and that these strands react as planned, that molecular biology protocols, such as PCR or affinity separation, correctly extract the result, and that sufficient flexibility remains so that worthwhile...

4.
Feedback control of traveling wave solutions of the complex Ginzburg Landau equation - K. A. Montgomery; M. Silber
Through a linear stability analysis, we investigate the effectiveness of a noninvasive feedback control scheme aimed at stabilizing traveling wave solutions Re iKx+iωt of the one-dimensional complex Ginzburg Landau equation (CGLE) in the Benjamin-Feir unstable regime. The feedback control is a generalization of the time-delay method of Pyragas [1], which was proposed by Lu, Yu and Harrison [2] in the setting of nonlinear optics. It involves both spatial shifts, by the wavelength of the targeted traveling wave, and a time delay that coincides with the temporal period of the traveling wave. We derive a single necessary and sufficient stability criterion...

5.
Some Forbidden Patterns in Automata for Dot-Depth One Languages - Heinz Schmitz
We deal with the class B 1 of dot-depth one languages which forms level one of the so-called dot-depth hierarchy. For some fixed alphabet A with jAj 2, a language L ` A + is in the class B 1 if and only if it can be expressed as a Boolean combination of languages u 0 A u 1 A u 2 A \Delta \Delta \Delta A un\Gamma1 A un , where u i 2 A and n 0. This class is the highest level of the dot-depth hierarchy known to be decidable up to now and a number of...

6.
Maximum Entropy Methods for Biological Sequence Modeling - Eugen C. Buehler; Lyle H. Ungar
Many of the same modeling methods used in natural languages, specifically Markov models and HMM's, have also been applied to biological sequence analysis. In recent years, natural language models have been improved upon by using maximum entropy methods which allow information based upon the entire history of a sequence to be considered. This is in contrast to the Markov models, whose predictions generally are based on some xed number of previous emissions, that have been the standard for most biological sequence models. To test the utility of Maximum Entropy modeling for biological sequence analysis, we used these methods to model...

7.
Improving N-Gram Modeling Using Distance-Related Unit Association Maximum Entropy Language Modeling - Shuwu Zhang; Harald Singer; Dekai Wu; Yoshinori Sagisaka
In this paper, a distance-related unit association maximum entropy (DUAME) language modeling is proposed. This approach can model an event (unit subsequence) using the co-occurrence of full distance unit association (UA) features so that it is able to pursue a functional approximation to higher order N-gram with significantly less memory requirement. A smoothing strategy related to this modeling will also be discussed. Preliminary experimental results have shown that DUAME modeling is comparable to conventional N-gram modeling in perplexity with significantly small number of parameters.

9.
Homoclinic and heteroclinic bifurcations in vector fields - Ale Jan Homburg; Björn Sandstede
An overview of homoclinic and heteroclinic bifurcation theory for autonomous vector fields is given. Specifically, homoclinic and heteroclinic bifurcations of codimension one and two in generic, equivariant, reversible, and conservative systems are reviewed, and results pertaining to the existence of multi-round homoclinic and periodic orbits and of complicated dynamics such as suspended horseshoes and attractors are stated. Bifurcations of homoclinic orbits from equilibria in local bifurcations are also considered. The main analytic and geometric techniques such as Lin’s method, Shil’nikov variables and homoclinic center manifolds for analyzing these bifurcations are discussed. Finally, a few related topics, such as topological moduli,...

10.
An Improved Molecular Solution for the Partition Problem - Xu Zhou; ShuangShuang Huang
Now the algorithms based on DNA computing for partition problem always converted the elements into binary number and then carry on mathematics operations on them. In this paper, our main purpose is to give an improved molecular solution for the partition problem. Our new algorithm does not need mathematics operations. So the algorithm is easier and the number of the operation is reduced. Besides, the time used in the biological experiment is less than before. In order to achieve this, we design a new encoding method. We also design a special parallel searcher to search the legal DNA strands in...

11.
Classes of Representable Disjoint NP-Pairs - Olaf Beyersdorff
For a propositional proof system P we introduce the complexity class DNPP(P) of all disjoint NP-pairs for which the disjointness of the pair is efficiently provable in the proof system P. We exhibit structural properties of proof systems which make canonical NP-pairs associated with these proof systems hard or complete for DNPP(P). Moreover, we demonstrate that non-equivalent proof systems can have equivalent canonical pairs and that depending on the properties of the proof systems different scenarios for DNPP(P) and the reductions between the canonical pairs exist.

12.
Tuples of Disjoint NP-Sets (Extended Abstract) - Olaf Beyersdorff
Disjoint NP-pairs are a well studied complexity theoretic concept with important applications in cryptography and propositional proof complexity. In this paper we introduce a natural generalization of the notion of disjoint NP-pairs to disjoint k-tuples of NP-sets for k ≥ 2. We define subclasses of the class of all disjoint k-tuples of NP-sets. These subclasses are associated with a propositional proof system and possess complete tuples which are defined from the proof system. In our main result we show that complete disjoint NP-pairs exist if and only if complete disjoint k-tuples of NP-sets exist for all k ≥ 2. Further,...

13.
Tuples of Disjoint NP-Sets - Olaf Beyersdorff
Disjoint NP-pairs are a well studied complexity-theoretic concept with important applications in cryptography and propositional proof complexity. In this paper we introduce a natural generalization of the notion of disjoint NP-pairs to disjoint k-tuples of NP-sets for k ≥ 2. We define subclasses of the class of all disjoint k-tuples of NP-sets. These subclasses are associated with a propositional proof system and possess complete tuples which are defined from the proof system. In our main result we show that complete disjoint NP-pairs exist if and only if complete disjoint k-tuples of NP-sets exist for all k ≥ 2. Further, this...

14.
Unifying runtime adaption and . . . - Brice Morin; Thomas Ledoux; Mahmoud Ben Hassine; Franck Chauvel; Olivier Barais; Jean-marc Jézéquel
The increasing need for continuously available software systems has raised two key-issues: self-adaptation and design evolution. The former one requires software systems to monitor their execution platform and automatically adapt their configuration and/or architecture to adjust their quality of service (optimization, fault-handling). The later one requires new design decisions to be reflected on the fly on the running system to ensure the needed high availability (new requirements, corrective and preventive maintenance). However, design evolution and self-adaptation are not independent and reflecting a design evolution on a running self-adaptative system is not always safe. We propose to unify run-time adaptation and...

15.
A DNA-Based Solution to the Subgraph Isomorphism Problem - Sun-yuan Hsieh; Chao-wen Huang
Since the experimental demonstration of its feasibility, DNA-based computing has been applied to a number of decision or combinatorial optimization problems. The graph isomorphism problem belongs to the class of NP problems, and has been conjectured intractable, although probably not NP-complete. In this paper, we demonstrate the power of DNA-based computing by showing the subgraph isomorphism problem can be efficiently solved under this computation model. By generating the solution space using stickers, we present DNA-based algorithms to solve the problem using polynomial number of basic biological operations.

16.
Finite semigroups and recognizable languages: an introduction - Jean-Eric Pin
This paper is an attempt to share with a larger audience some modern developments in the theory of finite automata. It is written for the mathematician who has a background in semigroup theory but knows next to nothing on automata and languages. No proofs are given, but the main results are illustrated by several examples and counterexamples. What is the topic of this theory? It deals with languages, automata and semigroups, although recent developments have shown interesting connections with model theory in logic, symbolic dynamics and topology. Historically, in their attempt to formalize natural languages, linguists such as Chomsky gave...

17.
EFFICIENT ALGORITHMS FOR MEMBERSHIP IN BOOLEAN HIERARCHIES OF REGULAR LANGUAGES - C. Glasser; H. Schmitz; V. Selivanov
The purpose of this paper is to provide efficient algorithms that decide membership for classes of several Boolean hierarchies for which efficiency (or even decidability) were previously not known. We develop new forbidden-chain characterizations for the single levels of these hierarchies and obtain the following results: • The classes of the Boolean hierarchy over level Σ1 of the dot-depth hierarchy are decidable in NL (previously only the decidability was known). The same remains true if predicates mod d for fixed d are allowed. • If modular predicates for arbitrary d are allowed, then the classes of the Boolean hierarchy over...

18.
Is Huffman Coding Dead? - A. Bookstein; S.T. Klein
In recent publications about data compression, arithmetic codes are often suggested as the state of the art, rather than the more popular Huffman codes. While it is true that Huffman codes are not optimal in all situations, we show that the advantage of arithmetic codes in compression performance is often negligible. Referring also to other criteria, we conclude that for many applications, Huffman codes should still remain a competitive choice.

19.
A Normalform for Classes of Concatenation Hierarchies - Christian Glaßer
Arbitrary regular languages can be expressed using Boolean operations, concatenation and the Kleene closure. If a regular language can be expressed without the Kleene closure, we call it starfree. A very interesting (and still open) problem is the following: Is there an algorithm computing the minimal number of alternations between Boolean operations and concatenation needed to de ne a given starfree language. This problem is called the dot-depth problem. Grouping together languages of the same concatenation complexity leads in a natural way to the definition of (infinite and strict) hierarchies that exhaust the class of starfree regular languages. The classes...

20.
Exploiting RDFS and OWL for Integrating Heterogeneous, Large-Scale, Linked Data Corpora - Aidan Hogan
The Web contains a vast amount of information on an abundance of topics, much of which is encoded as structured data indexed by local databases. However, these databases are rarely interconnected and information reuse across sites is limited. Semantic Web standards offer a possible solution in the form of an agreed-upon data model and set of syntaxes, as well as metalanguages for publishing schema-level information, offering a highly-interoperable means of publishing and interlinking structured data on the Web. Thanks to the Linked Data community, an unprecedented lode of such data has now been published on the Web—by individuals, academia, communities,...