首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 274 毫秒
1.
In this paper we deepen Mundici's analysis on reducibility of the decision problem from infinite-valued ukasiewicz logic to a suitable m-valued ukasiewicz logic m , where m only depends on the length of the formulas to be proved. Using geometrical arguments we find a better upper bound for the least integer m such that a formula is valid in if and only if it is also valid in m. We also reduce the notion of logical consequence in to the same notion in a suitable finite set of finite-valued ukasiewicz logics. Finally, we define an analytic and internal sequent calculus for infinite-valued ukasiewicz logic.  相似文献   

2.
Definability of Polyadic Lifts of Generalized Quantifiers   总被引:1,自引:1,他引:0  
We study generalized quantifiers on finite structures.With every function : we associate a quantifier Q by letting Q x say there are at least (n) elementsx satisfying , where n is the sizeof the universe. This is the general form ofwhat is known as a monotone quantifier of type < 1 >.We study so called polyadic liftsof such quantifiers. The particular lifts we considerare Ramseyfication, branching and resumption.In each case we get exact criteria fordefinability of the lift in terms of simpler quantifiers.  相似文献   

3.
The notion of the rational closure of a positive knowledge base K of conditional assertions | (standing for if then normally ) was first introduced by Lehmann (1989) and developed by Lehmann and Magidor (1992). Following those authors we would also argue that the rational closure is, in a strong sense, the minimal information, or simplest, rational consequence relation satisfying K. In practice, however, one might expect a knowledge base to consist not just of positive conditional assertions, | , but also negative conditional assertions, i (standing for not if then normally . Restricting ourselves to a finite language we show that the rational closure still exists for satisfiable knowledge bases containing both positive and negative conditional assertions and has similar properties to those exhibited in Lehmann and Magidor (1992). In particular an algorithm in Lehmann and Magidor (1992) which constructs the rational closure can be adapted to this case and yields, in turn, completeness theorems for the conditional assertions entailed by such a mixed knowledge base.  相似文献   

4.
The paper describes an improved algorithm for computing cohomologies of Lie (super)algebras. The original algorithm developed earlier by the author of this paper is based on the decomposition of the entire cochain complex into minimal subcomplexes. The suggested improvement consists in the replacement of the arithmetic of rational or integer numbers by a more efficient arithmetic of modular fields and the use of the relationship dim H k( p) dimH k() between the dimensions of cohomologies over an arbitrary modular field p = /p and the filed of rational numbers . This inequality allows us to rapidly find subcomplexes for which dimH k( p) > 0 (the number of such subcomplexes is usually not great) using computations over an arbitrary p and, then, carry out all required computations over in these subcomplexes.  相似文献   

5.
The I/O automaton paradigm of Lynch and Tuttle models asynchrony through an interleaving parallel composition. The recognition that such interleaving models in fact can be viewed as special cases of synchronous parallel composition has been very limited. Let be any set of finite-state I/O automata drawing actions from a fixed finite set containing a subset . In this article we establish a translation T : to a class of -automata closed under a synchronous parallel composition, for which T is monotonic with respect to implementation relative to , and linear with respect to composition. Thus, for A1, ..., A, B1, ..., B and A = A1 ... A, B = B1 ... B, if is the set of actions common to both A and B, then A implements B (in the sense of I/O automata) if and only if the -automaton language containment (T(A1) ... T(A)) (T(B1) ... T(B)) obtains, where denotes the interleaving parallel composition on and denotes the synchronous parallel composition on . For the class , we use the L-process model of -automata. This result enables one to verify systems specified by I/O automata through model-checkers such as COSPAN or SMV, that operate on models with synchronous parallel composition. The translation technique generalizes to other interleaving models, although in each case, the translation map must match the specific model.  相似文献   

6.
Any given n×n matrix A is shown to be a restriction, to the A-invariant subspace, of a nonnegative N×N matrix B of spectral radius (B) arbitrarily close to (A). A difference inclusion , where is a compact set of matrices, is asymptotically stable if and only if can be extended to a set of nonnegative matrices B with or . Similar results are derived for differential inclusions.  相似文献   

7.
In this paper, we investigate the numerical solution of a model equation u xx = exp(– ) (and several slightly more general problems) when 1 using the standard central difference scheme on nonuniform grids. In particular, we are interested in the error behaviour in two limiting cases: (i) the total mesh point number N is fixed when the regularization parameter 0, and (ii) is fixed when N. Using a formal analysis, we show that a generalized version of a special piecewise uniform mesh 12 and an adaptive grid based on the equidistribution principle share some common features. And the optimal meshes give rates of convergence bounded by |log()| as 0 and N is given, which are shown to be sharp by numerical tests.  相似文献   

8.
A linear evolution equation for a thermodynamic variable F, odd under time-reversal, is obtained from the exact equation derived by Robertson from the Liouville equation for the information-theoretic phase-space distribution. One obtains an exact expression for , the relaxation time for F. For very short , is time-independent for t > if C(t) F{exp(-i t)}Fo, the equilibrium time correlation, decays exponentially for t > . is the Liouville operator. So long as C(t) is such that decays rapidly to a steady-state value, the t limit of agrees with the fluctuation-dissipation theorem in applications to fluid transport.  相似文献   

9.
Conditions are presented under which the maximum of the Kolmogorov complexity (algorithmic entropy) K(1... N ) is attained, given the cost f( i ) of a message 1... N . Various extremal relations between the message cost and the Kolmogorov complexity are also considered; in particular, the minimization problem for the function f( i ) – K(1... N ) is studied. Here, is a parameter, called the temperature by analogy with thermodynamics. We also study domains of small variation of this function.  相似文献   

10.
A problem of estimating a functional parameter (x) and functionals () based on observation of a solution u (t, x) of the stochastic partial differential equation is considered. The asymptotic problem setting, as the noise intensity 0, is investigated.  相似文献   

11.
Summary We define a measure of complexity for (the group of permutations ofn elements). We thus obtain non trivial lower bounds for the number of Turing steps necessary for applaying a permutation to a tape withn entries. Transposing annxn matrix, for example, stored linearly needs at leastCn 2 Ign steps.  相似文献   

12.
Difficulties often arise in analyzing stochastic discrete event systems due to the so-called curse of dimensionality. A typical example is the computation of some integer-parameterized functions, where the integer parameter represents the system size or dimension. Rational approximation approach has been introduced to tackle this type of computational complexity. The underline idea is to develop rational approximants with increasing orders which converge to the values of the systems. Various examples demonstrated the effectiveness of the approach. In this paper we investigate the convergence and convergence rates of the rational approximants. First, a convergence rate of order O(1/ ) is obtained for the so-called Type-1 rational approximant sequence. Secondly, we establish conditions under which the sequence of [n/n] Type-2 rational approximants has a convergence rate of order .  相似文献   

13.
Danqing  Zhang  Weiguo  Li  Zuhe  Shen 《Reliable Computing》1999,5(1):23-33
In this paper, we use the concepts of {1} - and {2} -inverse of a matrix to construct such a Krawczyk-like operator as
where Y Rnxm, and A Rmxn satisfies YAY = Y. We also construct a generalized Krawczyk-Moore algorithm using this operator. Our main result is that, under the conditions there is a unique solution of Yf(x) = 0 on X {x + R(Y)} , and the generalized Krawczyk-Moore algorithm converges to this solution at least linearly.  相似文献   

14.
Let be some set of orientations, that is, . We consider the consequences of defining visibility based on curves that are monotone with respect to the orientations in . We call such curves -staircases. Two points p andq in a polygonP are said to -see each other if an -staircase fromp toq exists that is completely contained inP. The -kernel of a polygonP is then the set of all points which -see all other points. The -kernel of a simple polygon can be obtained as the intersection of all {}-kernels, with . With the help of this observation we are able to develop an algorithm to compute the -kernel of a simple polygon, for finite . We also show how to compute theexternal -kernel of a polygon in optimal time . The two algorithms are combined to compute the ( -kernel of a polygon with holes in time .This work was supported by the Deutsche Forschungsgemeinschaft under Grant No. Ot 64/5-4 and the Natural Sciences and Engineering Research Council of Canada and Information Technology Research Centre of Ontario.  相似文献   

15.
Given a nonempty set of functions
where a = x 0 < ... < x n = b are known nodes and w i , i = 0,...,n, d i , i = 1,..., n, known compact intervals, the main aim of the present paper is to show that the functions and
exist, are in F, and are easily computable. This is achieved essentially by giving simple formulas for computing two vectors with the properties
] is the interval hull of (the tolerance polyhedron) T; iff T 0 iff F 0. , can serve for solving the following problem: Assume that is a monotonically increasing functional on the set of Lipschitz-continuous functions f : [a,b] R (e.g. (f) = a b f(x) dx or (f) = min f([a,b]) or (f) = max f([a,b])), and that the available information about a function g : [a,b] R is "g F," then the problem is to find the best possible interval inclusion of (g). Obviously, this inclusion is given by the interval [( ,( )]. Complete formulas for computing this interval are given for the case (f) = a b f(x) dx.  相似文献   

16.
In this paper, we discuss the minimal number of observables Q 1, ..., Q , where expectation values at some time instants t 1, ..., t r determine the trajectory of a d-level quantum system (qudit) governed by the Gaussian semigroup . We assume that the macroscopic information about the system in question is given by the mean values E j(Q i) = tr(Q i(t j)) of n selfadjoint operators Q 1, ..., Q n at some time instants t 1 < t 2 < ... < t r, where n < d 2– 1 and r deg (, ). Here (, ) stands for the minimal polynomial of the generator of the Gaussian flow (t).  相似文献   

17.
We consider regular mathematical programming problems of the form f(x, y) inf, y F(x), x Rn, where F(x) = {y Rm hi| (x, y) 0, , hi (x, y) = 0, . The directional derivatives offunctions (x) = inf{f(x, y)|y F(x)} are estimated.Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 70–77, November–December, 1991.  相似文献   

18.
The population dynamics model , was considered. For this model with uniform distribution of delays and a n = 0, nonnegativeness and convexity of the sequence a k (0 k n) was shown to be the sufficient stability condition. Therefore, there is no need to constrain the reproduction rate and the mean delay .  相似文献   

19.
Given an integerk, and anarbitrary integer greater than , we prove a tight bound of on the time required to compute with operations {+, –, *, /, ·, }, and constants {0, 1}. In contrast, when the floor operation is not available this computation requires (k) time. Using the upper bound, we give an time algorithm for computing log loga, for alln-bit integersa. This upper bound matches the lower bound for computing this function given by Mansour, Schieber, and Tiwari. To the best of our knowledge these are the first non-constant tight bounds for computations involving the floor operation.  相似文献   

20.
Subsumption is an important redundancy elimination method in automated deduction. A clause D is subsumed by a set of clauses if there is a clause C and a substitution such that the literals of C are included in D. In the field of automated model building, subsumption has been modified to an even stronger redundancy elimination method, namely the so-called clausal H-subsumption. Atomic H-subsumption emerges from clausal H-subsumption by restricting D to an atom and to a set of atoms. Both clausal and atomic H-subsumption play an indispensable key role in automated model building. Moreover, problems equivalent to atomic H-subsumption have been studied with different terminologies in many areas of computer science. Both clausal and atomic H-subsumption are known to be intractable, i.e., p 2 -complete and NP-complete, respectively. In this paper, we present a new approach to deciding (clausal and atomic) H-subsumption that is based on a reduction to QSAT2 and SAT, respectively.This was partially supported by the Austrian Science Foundation under grant P15068. We thank the anonymous referees for valuable comments.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号