共查询到20条相似文献,搜索用时 46 毫秒
1.
The Feedback Vertex Set problem on unweighted, undirected graphs is considered. Improving upon a result by Burrage et al. (Proceedings 2nd International
Workshop on Parameterized and Exact Computation, pp. 192–202, 2006), we show that this problem has a kernel with O(k
3) vertices, i.e., there is a polynomial time algorithm, that given a graph G and an integer k, finds a graph G′ with O(k
3) vertices and integer k′≤k, such that G has a feedback vertex set of size at most k, if and only if G′ has a feedback vertex set of size at most k′. Moreover, the algorithm can be made constructive: if the reduced instance G′ has a feedback vertex set of size k′, then we can easily transform a minimum size feedback vertex set of G′ into a minimum size feedback vertex set of G. This kernelization algorithm can be used as the first step of an FPT algorithm for Feedback Vertex Set, but also as a preprocessing heuristic for Feedback Vertex Set. 相似文献
2.
A homomorphism (?) of logic programs from P to P' is a function mapping Atoms(P) to Atoms(P') and it preserves complements and program clauses. For each definite program clause a←a1,...,an∈P it implies that (?)(a)←(?)(a1),...,(?)(an) is a program clause of P'. A homomorphism (?) is an isomorphism if (?) is a bijection. In this paper, the complexity of the decision problems on homomorphism and isomorphism for definite logic programs is studied. It is shown that the homomorphism problem (HOM-LP) for definite logic programs is NP-complete, and the isomorphism problem (ISO-LP) is equivalent to the graph isomorphism problem (GI). 相似文献
3.
Francisco J. López Fraguas Mario Rodríguez Artalejo Rafael del Vado Vírseda 《Higher-Order and Symbolic Computation》2007,20(1-2):73-122
In this paper we propose a new generic scheme CFLP풟, intended as a logical and semantic framework for lazy Constraint Functional Logic Programming over a parametrically given
constraint domain 풟. As in the case of the well known CLP풟 scheme for Constraint Logic Programming, 풟 is assumed to provide domain specific data values and constraints. CFLP풟 programs are presented as sets of constrained rewrite rules that define the behavior of possibly higher order and/or non-deterministic
lazy functions over 풟. As a main novelty w.r.t. previous related work, we present a Constraint Rewriting Logic CRWL풟 which provides a declarative semantics for CFLP풟 programs. This logic relies on a new formalization of constraint domains and program interpretations, which allows a flexible
combination of domain specific data values and user defined data constructors, as well as a functional view of constraints.
This research has been partially supported by the Spanish National Projects MELODIAS (TIC2002-01167), MERIT-FORMS (TIN2005-09207-C03-03)
and PROMESAS-CAM (S-0505/TIC/0407). 相似文献
4.
Databases with uncertainty and lineage 总被引:2,自引:0,他引:2
Omar Benjelloun Anish Das Sarma Alon Halevy Martin Theobald Jennifer Widom 《The VLDB Journal The International Journal on Very Large Data Bases》2008,17(2):243-264
This paper introduces uldbs, an extension of relational databases with simple yet expressive constructs for representing and manipulating both lineage and uncertainty. Uncertain data and data lineage are two important areas of data management that have been considered extensively in isolation,
however many applications require the features in tandem. Fundamentally, lineage enables simple and consistent representation
of uncertain data, it correlates uncertainty in query results with uncertainty in the input data, and query processing with
lineage and uncertainty together presents computational benefits over treating them separately. We show that the uldb representation is complete, and that it permits straightforward implementation of many relational operations. We define two notions of uldb minimality—data-minimal and lineage-minimal—and study minimization of uldb representations under both notions. With lineage, derived relations are no longer self-contained: their uncertainty depends
on uncertainty in the base data. We provide an algorithm for the new operation of extracting a database subset in the presence
of interconnected uncertainty. We also show how uldbs enable a new approach to query processing in probabilistic databases. Finally, we describe the current state of the Trio system, our implementation of uldbs under development at Stanford.
This work was supported by the National Science Foundation under grants IIS-0324431, IIS-1098447, and IIS-9985114, by DARPA
Contract #03-000225, and by a grant from the Boeing Corporation. 相似文献
5.
Zusammenfassung Die Arbeit liefert einen Beitrag zur derLense'schen Vermutung über die Bewegung der Doppelnullstellen der AbleitungI′
ν (z) der Besselfunktionen bei ver?nderlichem negativen ν.
Mit 3 Textabbildungen
HerrnJ. Lense zum 75. Geburtstag gewidmet. 相似文献
Summary This paper gives a contribution to the hypothesis ofLense regarding the movements of the second order zeros of the derivativesI′ ν (z) of Bessel functions for every negativ variable ν.
Mit 3 Textabbildungen
HerrnJ. Lense zum 75. Geburtstag gewidmet. 相似文献
6.
The octagon abstract domain 总被引:2,自引:0,他引:2
Antoine Miné 《Higher-Order and Symbolic Computation》2006,19(1):31-100
This article presents the octagon abstract domain, a relational numerical abstract domain for static analysis by abstract interpretation. It allows representing conjunctions
of constraints of the form ± X ± Y ≤ c where X and Y range among program variables and c is a constant in ℤ, ℚ, or ℝ automatically inferred. Abstract elements are represented using modified Difference Bound Matrices
and we use a normalization algorithm loosely based on the shortest-path closure to compute canonical representations and construct
best-precision abstract transfer functions. We achieve a quadratic memory cost per abstract element and a cubic worst-case
time cost per abstract operation, with respect to the number of program variables.
In terms of cost and precision, our domain is in between the well-known fast but imprecise interval domain and the costly
polyhedron domain. We show that it is precise enough to treat interesting examples requiring relational invariants, and hence, out of the reach of the interval domain. We also present a packing strategy that allows scaling our domain up to large programs by tuning the amount of relationality. The octagon domain was
incorporated into the ASTRéE industrial-strength static analyzer and was key in proving the absence of run-time errors in large critical embedded flight
control software for Airbus planes.
This paper is the journal version of an earlier conference paper [44] sharing this title. However, the present version, extracted
from the author’s PhD [46] is extended in many ways and enriched with new experimental results.
Partially supported by the exploratory project ASTRéE of the Réseau National de recherche et d’innovation en Technologies Logicielles (RNTL). 相似文献
7.
Weighted Mean of a Pair of Graphs 总被引:1,自引:0,他引:1
G and G′, with d(G, G′) being the edit distance of G and G′, the weighted mean of G and G′ is a graph G″ that has edit distances d(G, G″) and d(G″, G′) to G and G′, respectively, such that d(G, G″) + d(G″, G′) = d(G,G′). We'll show formal properties of the weighted mean, describe a procedure for its computation, and give examples.
Received April 9, 2001 相似文献
8.
Peter Benner Vicente Hernández Antonio Pastor 《Mathematics of Control, Signals, and Systems (MCSS)》2003,16(1):76-93
We consider the computation of Hermitian nonnegative definite solutions of algebraic Riccati equations. These solutions are
the limit, P=limi →∞ P
i, of a sequence of matrices obtained by solving a sequence of Lyapunov equations. The procedure parallels the well-known Kleinman
technique but the stabilizability condition on the underlying linear time-invariant system is removed. The convergence of
the constructed sequence {P
i }i≥1 is guaranteed by the minimality of P
i in the set of Hermitian nonnegative definite solutions of the Lyapunov equation in the ith iteration step.
Date received: October 21, 1999. Date revised: February 14, 2002.
RID="*"
ID="*"This work was supported by the Acciones Integradas programme of Deutscher Akademischer Austauschdienst (Germany) and
Dirección General de Infraestructura y Relaciones Internacionales (Spain). 相似文献
9.
Let P(d) be a program implementing a partial recursive function φ. Let $
\mathcal{O}
$
\mathcal{O}
P
denote a function defined on the domain of function φ that maps an input data d
0 onto the path of computation of P on the input d
0. Let Q(p, d) be a program returning a value if and only if p = $
\mathcal{O}
$
\mathcal{O}
P
(d), and let the value of the program be Q($
\mathcal{O}
$
\mathcal{O}
P
(d), d) = P(d). Program Q(p, d), which is totally absurd from the point of view of its practical computation on concrete input data, may be practically
useful when it is analyzed by a metaprogram. It is shown in the paper how program Q(p, d) can be used for verification of a postcondition imposed on program P(d). The proposed method was tested on verification tasks for cache coherence protocols and other distributed computing systems. 相似文献
10.
Alternating-time temporal logic (atl) is a logic for reasoning about open computational systems and multi-agent systems. It is well known that atl model checking is linear in the size of the model. We point out, however, that the size of an atl model is usually exponential in the number of agents. When the size of models is defined in terms of states and agents rather than transitions, it turns out that the problem is (1) Δ
3
P
-complete for concurrent game structures, and (2) Δ
2
P
-complete for alternating transition systems. Moreover, for “Positive atl” that allows for negation only on the level of propositions, model checking is (1) Σ
2
P
-complete for concurrent game structures, and (2) NP-complete for alternating transition systems. We show a nondeterministic polynomial reduction from checking arbitrary alternating
transition systems to checking turn-based transition systems, We also discuss the determinism assumption in alternating transition
systems, and show that it can be easily removed.
In the second part of the paper, we study the model checking complexity for formulae of atl
with imperfect information (atl
ir
). We show that the problem is Δ
2
P
-complete in the number of transitions and the length of the formula (thereby closing a gap in previous work of Schobbens
in Electron. Notes Theor. Comput. Sci. 85(2), 2004). Then, we take a closer look and use the same fine structure complexity measure as we did for atl with perfect information. We get the surprising result that checking formulae of atl
ir
is also Δ
3
P
-complete in the general case, and Σ
2
P
-complete for “Positive atl
ir
”. Thus, model checking agents’ abilities for both perfect and imperfect information systems belongs to the same complexity
class when a finer-grained analysis is used. 相似文献
11.
This paper resolved an open problem proposed by A .P. Stolboushkin and M .A. Taitslin.We studied the expressibility of first order dynamic logic, and constructed infinite recursive programclasses K_1 , K_2, …, RG K_1 K_2 … RF, such that L (RG)相似文献
12.
Fast Algorithms for the Density Finding Problem 总被引:1,自引:0,他引:1
We study the problem of finding a specific density subsequence of a sequence arising from the analysis of biomolecular sequences.
Given a sequence A=(a
1,w
1),(a
2,w
2),…,(a
n
,w
n
) of n ordered pairs (a
i
,w
i
) of numbers a
i
and width w
i
>0 for each 1≤i≤n, two nonnegative numbers ℓ, u with ℓ≤u and a number δ, the Density Finding Problem is to find the consecutive subsequence A(i
*,j
*) over all O(n
2) consecutive subsequences A(i,j) with width constraint satisfying ℓ≤w(i,j)=∑
r=i
j
w
r
≤u such that its density
is closest to δ. The extensively studied Maximum-Density Segment Problem is a special case of the Density Finding Problem with δ=∞. We show that the Density Finding Problem has a lower bound Ω(nlog n) in the algebraic decision tree model of computation. We give an algorithm for the Density Finding Problem that runs in optimal O(nlog n) time and O(nlog n) space for the case when there is no upper bound on the width of the sequence, i.e., u=w(1,n). For the general case, we give an algorithm that runs in O(nlog 2
m) time and O(n+mlog m) space, where
and w
min=min
r=1
n
w
r
. As a byproduct, we give another O(n) time and space algorithm for the Maximum-Density Segment Problem.
Grants NSC95-2221-E-001-016-MY3, NSC-94-2422-H-001-0001, and NSC-95-2752-E-002-005-PAE, and by the Taiwan Information Security
Center (TWISC) under the Grants NSC NSC95-2218-E-001-001, NSC95-3114-P-001-002-Y, NSC94-3114-P-001-003-Y and NSC 94-3114-P-011-001. 相似文献
13.
Zhi-Zhong Chen 《Algorithmica》2008,51(1):1-23
The Degree-
Δ
Closest Phylogenetic
k
th Root Problem (ΔCPR
k
) is the problem of finding a (phylogenetic) tree T from a given graph G=(V,E) such that (1) the degree of each internal node in T is at least 3 and at most Δ, (2) the external nodes (i.e. leaves) of T are exactly the elements of V, and (3) the number of disagreements, i.e., |E
⊕{{u,v} : u,v are leaves of T and d
T
(u,v)≤k}|, is minimized, where d
T
(u,v) denotes the distance between u and v in tree T. This problem arises from theoretical studies in evolutionary biology and generalizes several important combinatorial optimization
problems such as the maximum matching problem. Unfortunately, it is known to be NP-hard for all fixed constants Δ,k such that either both Δ≥3 and k≥3, or Δ>3 and k=2. This paper presents a polynomial-time 8-approximation algorithm for Δ
CPR
2 for any fixed Δ>3, a quadratic-time 12-approximation algorithm for 3CPR
3, and a polynomial-time approximation scheme for the maximization version of Δ
CPR
k
for any fixed Δ and k. 相似文献
14.
Maria Blesa Daniel Calzada Antonio Fernández Luis López Andrés L. Martínez Agustín Santos Maria Serna Christopher Thraves 《Theory of Computing Systems》2009,44(3):304-331
In this paper we initiate the generalization of the Adversarial Queueing Theory (aqt) model to capture the dynamics of continuous scenarios in which the usually assumed synchronicity of the evolution is not
required anymore. We propose an asynchronous model, named continuous
aqt (caqt), in which packets can have arbitrary lengths, and the network links may have different speeds (or bandwidths) and propagation
delays. With respect to the standard aqt model, these new features turn out to be significant for the stability of packet scheduling policies that take them into
account, but not so much for the stability of networks.
From the network point of view, we show that networks with directed acyclic topologies are universally stable, i.e., stable
independently of the scheduling policies and traffic patterns used in it. Interestingly enough, this even holds for traffic
patterns that make links to be fully loaded. Finally, it turns out that the set of universally stable networks remains the
same as in the aqt model and, therefore, the property of universal stability of networks is decidable in polynomial time.
Concerning packet scheduling policies, we show that the well-known lis, sis, ftgand nfsscheduling policies remain universally stable in the caqt model. We introduce other scheduling policies that, although being universally stable in the aqt model, they are unstable under the caqt model.
This work was partially supported by eu IST-2004-15964 (aeolus), by the Spanish Ministry of Education and Science under cicyt
tin2005-09198 (asce) and cicyt
tin2005-25859-E, by the Regional Government of Madrid under contract No. 07T/0022/2003, and by the Universidad Rey Juan Carlos
under project No. PPR-2004-42. Also partially supported by the Universidad de Chile (Mecesup fellowship and Anillo en Redes).
A preliminary version of this work was presented in the 30th International Symposium on Mathematical Foundations of Computer Science (mfcs), Gdansk, Poland, LNCS, vol. 3618, pp. 144–155, Springer. 相似文献
15.
I. Tomescu 《Calcolo》1978,15(1):1-15
Résumé Le but de ce travail est celui d'obtenir une borne inférieure de la longueur des plus longues cycles élémentaires pour un
graphe ou un hypergraphe de nombre chromatique donné.
Ainsi on démontre que tout graphe qui n'a pas (r+1)-cliques, de degré minimal ≥d (ou de nombre chromatiqued+1) contient un cycle élémentaire de longueur ≥rd/(r−1) et tout hypergrapheH de nombre chromatique χ(H)=k contient un cycle élémentaire de longueur ≥k. On obtient aussi que tout grapheG de nombre chromatique γ(G)=k≥3 qui n'a pas de triangles contient un cycle élémentaire de longueur ≥2k−1, résultat qui est généralisé sous la forme suivante: Si le grapheG de degré minimal ≥d est 2-connexe et ne contient pas de triangles, alorsG=K
d,d′
oùd′≥d, ouG contient un cycle élémentaire de longueur ≥2d+1. On déduit que tout grapheG avec γ(G)=k≥3, qui n'a pask-cliques contient un cycle élémentaire de longueur ≥k+2, cette borne étant atteinte.
The aim of this paper is that to obtain a lower bound of the length of the longest elementary cycles of ak-chromatic graph or hypergraph. It is proved that any graph without (r+1)-cliques, having the minimal degree of its vertices ≥d (or the chromatic number equal tod+1) has an elementary cycle of length ≥rd/(r−1) and any hypergraphH of chromatic number χ(H)=k has an elementary cycle of length ≥k. It is obtained also that any graphG without triangles, having chromatic number γ(G)=k≥3 contains an elementary cycle of length ≥2k−1. This result is generalized in the following way: IfG is 2-connected, has minimal degree ≥d and contains no triangle, thenG=K d,d′ withd′≥d orG has an elementary cycle of length ≥2d+1. It is derived that any graphG with γ(G)=k≥3 which does not containk-cliques has an elementary cycle of length ≥k+2, this bound being attained.相似文献
16.
Class Refinement as Semantics of Correct Object Substitutability 总被引:2,自引:0,他引:2
Subtype polymorphism, based on syntactic conformance of objects' methods and used for substituting subtype objects for supertype
objects, is a characteristic feature of the object-oriented programming style. While certainly very useful, typechecking of
syntactic conformance of subtype objects to supertype objects is insufficient to guarantee correctness of object substitutability.
In addition, the behaviour of subtype objects must be constrained to achieve correctness. In class-based systems classes specify
the behaviour of the objects they instantiate. In this paper we define the class refinement relation which captures the semantic
constraints that must be imposed on classes to guarantee correctness of substitutability in all clients of the objects these
classes instantiate. Clients of class instances are modelled as programs making an iterative choice over invocation of class
methods, and we formally prove that when a class C′ refines a class C, substituting instances of C′ for instances of C is refinement for the clients.
Received May 1999 / Accepted in revised form March 2000 相似文献
17.
In the Π-Cluster Editing problem, one is given an undirected graph G, a density measure Π, and an integer k≥0, and needs to decide whether it is possible to transform G by editing (deleting and inserting) at most k edges into a dense cluster graph. Herein, a dense cluster graph is a graph in which every connected component K=(V
K
,E
K
) satisfies Π. The well-studied Cluster Editing problem is a special case of this problem with Π:=“being a clique”. In this work, we consider three other density measures
that generalize cliques: (1) having at most s missing edges (s-defective cliques), (2) having average degree at least |V
K
|−s (average-s-plexes), and (3) having average degree at least μ⋅(|V
K
|−1) (μ-cliques), where s and μ are a fixed integer and a fixed rational number, respectively. We first show that the Π-Cluster Editing problem is NP-complete for all three density measures. Then, we study the fixed-parameter tractability of the three clustering
problems, showing that the first two problems are fixed-parameter tractable with respect to the parameter (s,k) and that the third problem is W[1]-hard with respect to the parameter k for 0<μ<1. 相似文献
18.
Michiro Kondo Wieslaw A. Dudek 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2008,12(11):1035-1037
In this short paper we shall prove that every bounded lattice L with the conditions: (c1) 1′ = 0 and (EL): (a · b′)′ = b + a′ · b′ for all a, b ∈ L is a Boolean algebra. This is a more general result than that of Renedo et al. (Proceedings NAFIPS’04, 2004), in which it
is proved that every orthocomplemented lattice with (EL) is a Boolean algebra. 相似文献
19.
A new private set-operation problem is proposed. Suppose there are n parties with each owning a secret set. Let one of them, say P, be the leader, S be P's secret set, and t (less than n - 1) be a threshold value. For each element w of S, if w appears more than t times in the rest parties' sets, then P learns which parties' sets include w, otherwise P cannot know whether w appears in any party's set. For this problem, a secure protocol is proposed in the semi-honest model based on semantically secure homomorphic encryption scheme, secure sharing scheme, and the polynomial representation of sets. The protocol only needs constant rounds of communication. 相似文献
20.
Liveness temporal properties state that something “good” eventually happens, e.g., every request is eventually granted. In
Linear Temporal Logic (LTL), there is no a priori bound on the “wait time” for an eventuality to be fulfilled. That is, F
θ asserts that θ holds eventually, but there is no bound on the time when θ will hold. This is troubling, as designers tend to interpret an eventuality F
θ as an abstraction of a bounded eventuality F
≤k
θ, for an unknown k, and satisfaction of a liveness property is often not acceptable unless we can bound its wait time. We introduce here prompt-LTL, an extension of LTL with the prompt-eventually operator F
p
. A system S satisfies a prompt-LTL formula φ if there is some bound k on the wait time for all prompt-eventually subformulas of φ in all computations of S. We study various problems related to prompt-LTL, including realizability, model checking, and assume-guarantee model checking, and show that they can be solved by techniques
that are quite close to the standard techniques for LTL. 相似文献