Search results for " Computer Science"
showing 10 items of 3983 documents
New Encodings of Pseudo-Boolean Constraints into CNF
2009
International audience; This paper answers affirmatively the open question of the existence of a polynomial size CNF encoding of pseudo-Boolean (PB) constraints such that generalized arc consistency (GAC) is maintained through unit propagation (UP). All previous encodings of PB constraints either did not allow UP to maintain GAC, or were of exponential size in the worst case. This paper presents an encoding that realizes both of the desired properties. From a theoretical point of view, this narrows the gap between the expressive power of clauses and the one of pseudo-Boolean constraints.
Theory of tailor automata
2019
Abstract In the paper, a fragment of the new theory of tailor automata is presented, within which a deterministic finite automaton was defined. The proposed automaton provides a theoretical model of an informally characterized biomolecular automaton. The idea of working of which is founded on the concept of alternating cut of some double-stranded fragments of DNA, with the use of a restriction enzyme and ligations of some double-stranded fragments of DNA, with the use of the ligase enzyme.
Timed Sets, Functional Complexity, and Computability
2012
AbstractThe construction of various categories of “timed sets” is described in which the timing of maps is considered modulo a “complexity order”. The properties of these categories are developed: under appropriate conditions they form discrete, distributive restriction categories with an iteration. They provide a categorical basis for modeling functional complexity classes and allow the development of computability within these settings. Indeed, by considering “program objects” and the functions they compute, one can obtain models of computability – i.e. Turing categories – in which the total maps belong to specific complexity classes. Two examples of this are introduced in some detail whi…
A genetic system based on simulated crossover of sequences of two-bit genes
2006
AbstractWe introduce a genetic model based on simulated crossover of fixed sequences of two-bit genes. Results are(1)a lower bound on population size is exhibited such that a transition takes the stochastic finite population genetic system near the next state of the deterministic infinite population genetic system (provided both begin in the same state);(2)states and dynamics of the deterministic infinite population genetic system are derived for arbitrary (finite) fitness functions (expressed in terms of multivariate polynomials);(3)in the case of quadratic fitness defined by weight matrices with m nonnull entries it is shown that each state transition can be implemented in time O(m+l), wh…
Finitary Representations and Images of Transitive Finitary Permutation Groups
1999
Abstract We characterize the point stabilizers and kernels of finitary permutation representations of infinite transitive groups of finitary permutations. Moreover, the number of such representations is determined.
Discrete wavelet transform based multispectral filter array demosaicking
2013
International audience; The idea of colour filter array may be adapted to multi-spectral image acquisition by integrating more filter types into the array, and developing associated demosaicking algorithms. Several methods employing discrete wavelet transform (DWT) have been proposed for CFA demosaicking. In this work, we put forward an extended use of DWT for mul-tispectral filter array demosaicking. The extension seemed straightforward, however we observed striking results. This work contributes to better understanding of the issue by demonstrating that spectral correlation and spatial resolution of the images exerts a crucial influence on the performance of DWT based demosaicking.
Robust stabilisation of 2D state-delayed stochastic systems with randomly occurring uncertainties and nonlinearities
2013
This paper is concerned with the state feedback control problem for a class of two-dimensional (2D) discrete-time stochastic systems with time-delays, randomly occurring uncertainties and nonlinearities. Both the sector-like nonlinearities and the norm-bounded uncertainties enter into the system in random ways, and such randomly occurring uncertainties and nonlinearities obey certain mutually uncorrelated Bernoulli random binary distribution laws. Sufficient computationally tractable linear matrix inequality–based conditions are established for the 2D nonlinear stochastic time-delay systems to be asymptotically stable in the mean-square sense, and then the explicit expression of the desired…
XML document-grammar comparison: related problems and applications
2011
10.2478/s13537-011-0005-1; International audience; XML document comparison is becoming an ever more popular research issue due to the increasingly abundant use of XML. Likewise, a growing interest fosters the development of XML grammar matching and comparison, due to the proliferation of heterogeneous XML data sources, particularly on the Web. Nonetheless, the process of comparing XML documents with XML grammars, i.e., XML document and grammar similarity evaluation, has not yet received the attention it deserves. In this paper, we provide an overview on existing research related to XML document/grammar comparison, presenting the background and discussing the various techniques related to th…
An overview on XML similarity: Background, current trends and future directions
2009
In recent years, XML has been established as a major means for information management, and has been broadly utilized for complex data representation (e.g. multimedia objects). Owing to an unparalleled increasing use of the XML standard, developing efficient techniques for comparing XML-based documents becomes essential in the database and information retrieval communities. In this paper, we provide an overview of XML similarity/comparison by presenting existing research related to XML similarity. We also detail the possible applications of XML comparison processes in various fields, ranging over data warehousing, data integration, classification/clustering and XML querying, and discuss some…
Extensible User-Based XML Grammar Matching
2009
International audience; XML grammar matching has found considerable interest recently due to the growing number of heterogeneous XML documents on the web and the increasing need to integrate, and consequently search and retrieve XML data originated from different data sources. In this paper, we provide an approach for automatic XML grammar matching and comparison aiming to minimize the amount of user effort required to perform the match task. We propose an open framework based on the concept of tree edit distance, integrating different matching criterions so as to capture XML grammar element semantic and syntactic similarities, cardinality and alternativeness constraints, as well as data-ty…