共查询到20条相似文献,搜索用时 93 毫秒
1.
Steven Givant 《Journal of Automated Reasoning》2006,37(4):277-322
A variable-free, equational logic $\mathcal{L}^\timesA variable-free, equational logic based on the calculus of relations (a theory of binary relations developed by De Morgan, Peirce, and Schr?der during the
period 1864–1895) is shown to provide an adequate framework for the development of all of mathematics. The expressive and
deductive powers of are equivalent to those of a system of first-order logic with just three variables. Therefore, three-variable first-order
logic also provides an adequate framework for mathematics. Finally, it is shown that a variant of may be viewed as a subsystem of sentential logic. Hence, there are subsystems of sentential logic that are adequate to the
task of formalizing mathematics.
This paper is an expanded version of a talk given by the author at the Special Session on Automated Reasoning in Mathematics
and Logic, held March 8–10, 2002, at the Georgia Institute of Technology, during the Joint Southeastern Section MAA/Southeast
Regional AMS Meeting. The session was organized by Johan G. F. Belinfante. 相似文献
2.
3.
4.
5.
Dmitry Tsarkov Ian Horrocks Peter F. Patel-Schneider 《Journal of Automated Reasoning》2007,39(3):277-316
6.
Olaf Beyersdorff 《Theory of Computing Systems》2008,43(2):118-135
Disjoint
-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
-pairs to disjoint k-tuples of
-sets for k≥2. We define subclasses of the class of all disjoint k-tuples of
-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
-pairs exist if and only if complete disjoint k-tuples of
-sets exist for all k≥2. Further, this is equivalent to the existence of a propositional proof system in which the disjointness of all k-tuples is shortly provable. We also show that a strengthening of this conditions characterizes the existence of optimal proof
systems.
An extended abstract of this paper appeared in the proceedings of the conference CSR 2006 (Lecture Notes in Computer Science
3967, 80–91, 2006).
Supported by DFG grant KO 1053/5-1. 相似文献
7.
We develop new techniques for the automated construction of models for subclasses of equational clausal logic. The models are represented by some specific class of rewrite rules. We show that the evaluation of arbitrary first-order formulae in these interpretations is a decidable problem. As an example of an application, we consider the class
, a decidable subclass of first-order clausal logic without equality. In the equational case,
is undecidable, but it is known to be decidable if all the equational literals are ground. We extend this result to a class of clause sets possibly containing nonground equational literals. The algorithms for extracting models from positively disconnected saturated sets proposed by Fermüller and Leitsch are extended in order to handle the full ordering restrictions of the resolution/paramodulation calculus. 相似文献
8.
Proving that a propositional formula is contradictory or unsatisfiable is a fundamental task in automated reasoning. This
task is coNP-complete. Efficient algorithms are therefore needed when formulae are hard to solve. Random
sat formulae provide a test-bed for algorithms because experiments that have become widely popular show clearly that these formulae
are consistently difficult for any known algorithm. Moreover, the experiments show a critical value of the ratio of the number
of clauses to the number of variables around which the formulae are the hardest on average. This critical value also corresponds
to a ‘phase transition’ from solvability to unsolvability. The question of whether the formulae located around or above this
critical value can efficiently be proved unsatisfiable on average (or even for a.e. formula) remains up to now one of the
most challenging questions bearing on the design of new and more efficient algorithms. New insights into this question could
indirectly benefit the solving of formulae coming from real-world problems, through a better understanding of some of the
causes of problem hardness. In this paper we present a solving heuristic that we have developed, devoted essentially to proving
the unsatisfiability of random
sat formulae and inspired by recent work in statistical physics. Results of experiments with this heuristic and its evaluation
in two recent sat competitions have shown a substantial jump in the efficiency of solving hard, unsatisfiable random
sat formulae. 相似文献
9.
Evan Goris 《Theory of Computing Systems》2008,43(2):185-203
This paper presents a semantics for the logic of proofs
in which all the operations on proofs are realized by feasibly computable functions. More precisely, we will show that the
completeness of
for the semantics of proofs of Peano Arithmetic extends to the semantics of proofs in Buss’ bounded arithmetic
. In view of applications in epistemology of
in particular and justification logics in general this result shows that explicit knowledge in the propositional framework
can be made computationally feasible.
This research supported by CUNY Community College Collaborative Incentive Research Grant 91639-0001 “Mathematical Foundations
of Knowledge Representation”. 相似文献
10.
José-Luis Ruiz-Reina Francisco-Jesús Martín-Mateos José-Antonio Alonso María-José Hidalgo 《Journal of Automated Reasoning》2006,37(1-2):67-92
We present a case study using ACL2 to verify a nontrivial algorithm that uses efficient data structures. The algorithm receives
as input two first-order terms, and it returns a most general unifier of these terms if they are unifiable, failure otherwise.
The verified implementation stores terms as directed acyclic graphs by means of a pointer structure. Its time complexity is
and its space complexity , and it can be executed in ACL2 at a speed comparable to a similar C implementation. We report the main issues encountered
to achieve this formally verified implementation.
This work has been supported by project TIN2004-03884 (Ministerio de Educación y Ciencia, Spain) and FEDER funds. 相似文献
11.
Dai, Li, and Wu proposed Rule k, a localized approximation algorithm that attempts to find a small connected dominating
set in a graph. In this paper we consider the "average-case" performance of two closely related versions of Rule k for the
model of random unit disk graphs constructed from n random points in an
square. We show that if
and
then for both versions of Rule k, the expected size of the Rule k dominating set is
as
It follows that, for
in a suitable range, the expected size of the Rule k dominating sets are within a constant factor of the optimum. 相似文献
12.
Tomasz Jurdziński 《Theory of Computing Systems》2009,45(1):74-107
Hardness of a separation of nondeterminism, randomization and determinism for polynomial time computations has motivated the
analysis of this issue for restricted models of computation. Following this line of research, we consider randomized length-reducing
two-pushdown automata (
), a natural extension of pushdown automata (
). Our main results are as follows. We show that deterministic
s are weaker than Las Vegas
s which in turn are weaker than Monte Carlo
s. Moreover, bounded two-sided error
s are stronger than Monte Carlo
s and they are able to recognize some languages which cannot be recognized nondeterministically. Finally, we prove that amplification
is impossible for Las Vegas and Monte Carlo automata.
Partially supported by MNiSW grant number N206 024 31/3826, 2006-2008. An extended abstract of this paper appeared in the
MFCS06 Proceedings (Lecture Notes in Computer Science, vol. 4162, pp. 561–572, 2006). 相似文献
13.
We study the problem of computing the k maximum sum subsequences. Given a sequence of real numbers
and an integer parameter k,
the problem involves finding the k largest values of
for
The problem for fixed k = 1, also known as the maximum sum subsequence problem, has received much attention in the literature
and is linear-time solvable. Recently, Bae and Takaoka presented a
-time algorithm for the k maximum sum subsequences problem. In this paper we design an efficient algorithm that solves the
above problem in
time in the worst case. Our algorithm is optimal for
and improves over the previously best known result for any value of the user-defined parameter k < 1. Moreover, our results
are also extended to the multi-dimensional versions of the k maximum sum subsequences problem; resulting in fast algorithms
as well. 相似文献
14.
We use Schnyder woods of 3-connected planar graphs to produce convex straight-line drawings
on a grid of size
The parameter
depends on the Schnyder wood used for the drawing. This parameter is in the range
The algorithm is a refinement of the face-counting algorithm; thus, in particular, the size of the grid is at most
The above bound on the grid size simultaneously matches or improves all previously known bounds for convex drawings, in particular
Schnyder's and the recent Zhang and He bound for triangulations and the Chrobak and Kant bound for 3-connected planar graphs.
The algorithm takes linear time. The drawing algorithm has been implemented and tested. The expected grid size for the drawing
of a random triangulation is close to
For a random 3-connected plane graph, tests show that the expected size of the drawing is
相似文献
15.
In this paper, the method of well-combined semantics and syntax proposed by Pavelka is applied to the research of the propositional
calculus formal system
. The partial constant values are taken as formulas, formulas are fuzzified in two manners of semantics and syntax, and inferring
processes are fuzzified. A sequence of new extensions {
} of the system
is proposed, and the completeness of
is proved. 相似文献
16.
Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas 总被引:1,自引:0,他引:1
Michael Alekhnovich Edward A. Hirsch Dmitry Itsykson 《Journal of Automated Reasoning》2005,35(1-3):51-72
DPLL (for Davis, Putnam, Logemann, and Loveland) algorithms form the largest family of contemporary algorithms for SAT (the propositional satisfiability problem) and are
widely used in applications. The recursion trees of DPLL algorithm executions on unsatisfiable formulas are equivalent to
treelike resolution proofs. Therefore, lower bounds for treelike resolution (known since the 1960s) apply to them. However,
these lower bounds say nothing about the behavior of such algorithms on satisfiable formulas. Proving exponential lower bounds
for them in the most general setting is impossible without proving P ≠ NP; therefore, to prove lower bounds, one has to restrict the power of branching heuristics. In this paper, we give exponential
lower bounds for two families of DPLL algorithms: generalized myopic algorithms, which read up to n
1−ε
of clauses at each step and see the remaining part of the formula without negations, and drunk algorithms, which choose a variable using any complicated rule and then pick its value at random.
★Extended abstract of this paper appeared in Proceedings of ICALP 2004, LNCS 3142, Springer, 2004, pp. 84–96.
†Supported by CCR grant CCR-0324906.
‡Supported in part by Russian Science Support Foundation, RAS program of fundamental research “Research in principal areas
of contemporary mathematics,” and INTAS grant 04-77-7173.
§Supported in part by INTAS grant 04-77-7173. 相似文献
17.
There has been much recent interest in the use of the earliest-deadline-first (
) algorithm for scheduling soft real-time sporadic task systems on identical multiprocessors. In hard real-time systems, a
significant disparity exists between
-based schemes and Pfair scheduling: on M processors, the worst-case schedulable utilization for all known
variants is approximately M/2, whereas it is M for optimal Pfair algorithms. This is unfortunate because
-based algorithms entail lower scheduling and task-migration overheads. However, such a disparity in schedulability can be
alleviated by easing the requirement that all deadlines be met, which may be sufficient for soft real-time systems. In particular,
in recent work, we have shown that if task migrations are not restricted, then
(i.e. , global
) can ensure bounded tardiness for a sporadic task system with no restrictions on total utilization. Unrestricted task migrations
in global
may be unappealing for some systems, but if migrations are forbidden entirely, then bounded tardiness cannot be guaranteed.
In this paper, we address the issue of striking a balance between task migrations and system utilization by proposing an algorithm
called
, which is based upon
and treads a middle path, by restricting, but not eliminating, task migrations. Specifically, under
, the ability to migrate is required for at most M−1 tasks, and it is sufficient that every such task migrate between two processors and at job boundaries only.
, like global
, can ensure bounded tardiness to a sporadic task system as long as the available processing capacity is not exceeded, but,
unlike global
, may require that per-task utilizations be capped. The required cap is quite liberal, hence,
should enable a wide range of soft real-time applications to be scheduled with no constraints on total utilization.
相似文献
UmaMaheswari C. DeviEmail: |
18.
Klaus Meer 《Theory of Computing Systems》2007,41(1):107-118
In [10] it was recently shown that
that is the existence of transparent long proofs for
was established. The latter denotes the class of real number decision problems verifiable in polynomial time as introduced
by Blum et al. [6]. The present paper is devoted to the question what impact a potential full real number
theorem
would have on approximation issues in the BSS model of computation. We study two natural optimization problems in the BSS
model. The first, denoted by MAX-QPS, is related to polynomial systems; the other, MAX-q-CAP, deals with algebraic circuits.
Our main results combine the PCP framework over
with approximation issues for these two problems. We also give a negative approximation result for a variant of the MAX-QPS
problem. 相似文献
19.
Tomasz Jurdziński Friedrich Otto František Mráz Martin Plátek 《Theory of Computing Systems》2008,42(4):488-518
The
-automaton is the weakest form of the nondeterministic version of the restarting automaton that was introduced by Jančar et al. to model the so-called analysis by reduction. Here it is shown that the class ℒ(R) of languages that are accepted by
-automata is incomparable under set inclusion to the class
of Church-Rosser languages and to the class
of growing context-sensitive languages. In fact this already holds for the class
of languages that are accepted by 2-monotone
-automata. In addition, we prove that already the latter class contains
-complete languages, showing that already the 2-monotone
-automaton has a surprisingly large expressive power.
The results of this paper have been announced at DLT 2004 in Auckland, New Zealand.
This work was mainly carried out while T. Jurdziński was visiting the University of Kassel, supported by a grant from the
Deutsche Forschungsgemeinschaft (DFG).
F. Mráz and M. Plátek were partially supported by the Grant Agency of the Czech Republic under Grant-No. 201/04/2102 and by
the program ‘Information Society’ under project 1ET100300517. F. Mráz was also supported by the Grant Agency of Charles University
in Prague under Grant-No. 358/2006/A-INF/MFF. 相似文献
20.
Abstract We obtain a multivariate extension of a classical result of Schoenberg on cardinal spline interpolation. Specifically, we
prove the existence of a unique function in
, polyharmonic of order p on each strip
,
, and periodic in its last n variables, whose restriction to the parallel hyperplanes
,
, coincides with a prescribed sequence of n-variate periodic data functions satisfying a growth condition in
. The constructive proof is based on separation of variables and on Micchelli’s theory of univariate cardinal
-splines.
Keywords: cardinal
-splines, polyharmonic functions, multivariable interpolation
Mathematics Subject Classification (2000): 41A05, 41A15, 41A63 相似文献