Search results for "Theoretical Computer Science"
showing 10 items of 1151 documents
Adding symbolic information to picture models: definitions and properties
2005
AbstractIn the paper we propose extensions of some picture models, such as colored, drawn and pixel pictures. Such extensions are conceived by observing that a picture may embed more information than the shape, such as colors, labels, etc., which can be represented by a symbol from an alphabet and can be associated to segments, points or pixels. New interesting issues derived from the introduction of symbols will be investigated together with some complexity and decidability questions for the proposed extensions.
On the Trustworthiness of Error-Correcting Codes
2007
The use of error-correcting codes protects data against accidental or intentional errors, but to what extent can a decoded message be trusted? To answer this question, one has to take the role of the receiver. First, the maximum number of errors Lambda acceptable for decoding is fixed. With the weight distribution, the probability of false decoding can be calculated, conditioned on such a Lambda-bounded strategy. This probability is a monotonously increasing function in the channel error probability p and in the maximum number of accepted errors Lambda. Therefore, pure error detection is more trustworthy than error correction. Moreover, for sufficiently small p, codes with the lexicographic…
Analog joint source-channel Multiple Description coding scheme over AWGN parallel channels
2011
We propose a low complexity analog joint source channel coding Multiple Description (MD) scheme for transmitting the symbols of a Gaussian source across a pair of independent AWGN channels. The outputs of these channels have each a separated receiver, whereas a third receiver has both outputs available. At the transmitter side, a pair of bandwidth-reduction analog mappings are used for joint source-channel coding. The presented scheme has the inherent advantage over digital MD schemes based on separation, that coding and decoding can be performed by using a single-letter (or symbol), a strategy that is very suitable for applications where latency originated by the digital compression and th…
Incremental Treatments of the Full Configuration Interaction Problem
2020
The recent many-body expanded full configuration interaction (MBE-FCI) method is reviewed by critically assessing its advantages and drawbacks in the context of contemporary near-exact electronic structure theory. Besides providing a succinct summary of the history of MBE-FCI to date within a generalized and unified theoretical setting, its finer algorithmic details are discussed alongside our optimized computational implementation of the theory. A selected few of the most recent applications of MBE-FCI are revisited, before we close by outlining its future research directions as well as its place among modern near-exact wave function-based methods.
Neighbor-Distinguishing k-tuple Edge-Colorings of Graphs
2009
AbstractThis paper studies proper k-tuple edge-colorings of graphs that distinguish neighboring vertices by their sets of colors. Minimum numbers of colors for such colorings are determined for cycles, complete graphs and complete bipartite graphs. A variation in which the color sets assigned to edges have to form cyclic intervals is also studied and similar results are given.
Debates with Small Transparent Quantum Verifiers
2014
We study a model where two opposing provers debate over the membership status of a given string in a language, trying to convince a weak verifier whose coins are visible to all. We show that the incorporation of just two qubits to an otherwise classical constant-space verifier raises the class of debatable languages from at most NP to the collection of all Turing-decidable languages (recursive languages). When the verifier is further constrained to make the correct decision with probability 1, the corresponding class goes up from the regular languages up to at least E.
The PASSI and Agile PASSI MAS Meta-models Compared with a Unifying Proposal
2005
A great number of processes for multi-agent systems design have been presented in last years to support the different approaches to agent-oriented design; each process is specific for a particular class of problems and it instantiates a specific MAS meta-model. These differences produce inconsistences and overlaps: a MAS meta-model may define a term not referred by another, or the same term can be used with a different meaning. We think that the lack of a standardization may cause a significant delay to the diffusion of the agent paradigm outside research context. Working for this unification goal, it is also necessary to define in unambiguous way the terms of the agent model and their rela…
On Duality in Learning and the Selection of Learning Teams
1996
AbstractPrevious work in inductive inference dealt mostly with finding one or several machines (IIMs) that successfully learn collections of functions. Herein we start with a class of functions and considerthe learner setof all IIMs that are successful at learning the given class. Applying this perspective to the case of team inference leads to the notion ofdiversificationfor a class of functions. This enable us to distinguish between several flavours of IIMs all of which must be represented in a team learning the given class.
Positive Versions of Polynomial Time
1998
Abstract We show that restricting a number of characterizations of the complexity class P to be positive (in natural ways) results in the same class of (monotone) problems, which we denote by posP . By a well-known result of Razborov, posP is a proper subclass of the class of monotone problems in P . We exhibit complete problems for posP via weak logical reductions, as we do for other logically defined classes of problems. Our work is a continuation of research undertaken by Grigni and Sipser, and subsequently Stewart; indeed, we introduce the notion of a positive deterministic Turing machine and consequently solve a problem posed by Grigni and Sipser.
The expressive power of the shuffle product
2010
International audience; There is an increasing interest in the shuffle product on formal languages, mainly because it is a standard tool for modeling process algebras. It still remains a mysterious operation on regular languages.Antonio Restivo proposed as a challenge to characterize the smallest class of languages containing the singletons and closed under Boolean operations, product and shuffle. This problem is still widely open, but we present some partial results on it. We also study some other smaller classes, including the smallest class containing the languages composed of a single word of length 2 which is closed under Boolean operations and shuffle by a letter (resp. shuffle by a l…