Search results for " Computer Science"
showing 10 items of 3983 documents
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.
Combining workload balance and patient priority maximisation in operating room planning through hierarchical multi-objective optimisation
2022
Abstract Previous analysis suggested the opportunity to consider the preferences of different stakeholders (hospital, patients, doctors and nurses) through the adoption of both patient priority maximisation and workload balance as performance criteria. The aim of this paper is to develop an effective and efficient solution approach for the operating room planning and scheduling capable to take into account the patient priority maximisation and workload balance criteria at the same time. This work is inspired by the need of a deeper understanding of the quality of the solutions obtained when a combination of the two criteria leads the OR planning decisions. Starting from a hierarchical multi…
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…
Noise-tolerant efficient inductive synthesis of regular expressions from good examples
1997
We present an almost linear time method of inductive synthesis restoring simple regular expressions from one representative (good) example. In particular, we consider synthesis of expressions of star-height one, where we allow one union operation under each iteration, and synthesis of expressions without union operations from examples that may contain mistakes. In both cases we provide sufficient conditions defining precisely the class of target expressions and the notion of good examples under which the synthesis algorithm works correctly, and present the proof of correctness. In the case of expressions with unions the proof is based on novel results in the combinatorics of words. A genera…
Stochastic Stability Analysis for Markovian Jump Neutral Nonlinear Systems
2012
In this paper, the stability problem is studied for a class of Markovian jump neutral nonlinear systems with time-varying delay. By Lyapunov-Krasovskii function approach, a novel mean-square exponential stability criterion is derived for the situations that the system's transition rates are completely accessible, partially accessible and non-accessible, respectively. Moreover, the developed stability criterion is extended to the systems with different bounded sector nonlinear constraints. Finally, some numerical examples are provided to illustrate the effectiveness of the proposed methods.
On a class of languages with holonomic generating functions
2017
We define a class of languages (RCM) obtained by considering Regular languages, linear Constraints on the number of occurrences of symbols and Morphisms. The class RCM presents some interesting closure properties, and contains languages with holonomic generating functions. As a matter of fact, RCM is related to one-way 1-reversal bounded k-counter machines and also to Parikh automata on letters. Indeed, RCM is contained in L-NFCM but not in L-DFCM, and strictly includes L-CPA. We conjecture that L-DFCM subset of RCM