A redex in a graph G is a triple r = (u, c, v) of distinct vertices that determine a 2-star. Shrinking r means deleting the center c and merging u with v into one vertex. Reduction of G entails shrinking all of its re...
详细信息
A redex in a graph G is a triple r = (u, c, v) of distinct vertices that determine a 2-star. Shrinking r means deleting the center c and merging u with v into one vertex. Reduction of G entails shrinking all of its redexes in a recursive way, and, at the same time, deleting all loops that are created during this process. It is shown that reduction can be implemented in O(m) time, where m is the number of edges in G.
Using the framework of formal theory of partial differential equations, we consider a method of computation of the m-Hilbert polynomial (i.e. Hilbert polynomial with multivariable), which generalizes the Seiler's ...
详细信息
Using the framework of formal theory of partial differential equations, we consider a method of computation of the m-Hilbert polynomial (i.e. Hilbert polynomial with multivariable), which generalizes the Seiler's theorem of Hilbert polynomial with single variable. Next we present an approach to compute the number of arbitrary functions of positive differential order in the general solution, and give a formally well-posed initial problem. Finally,as applications the Maxwell equations and weakly over determined equations are considered.
Disjoint NP-pairs are an interesting model of computation with important applications in cryptography and proof complexity. the question whether there exists a complete disjoint NP-pair was posed by Razborov in 1994 a...
详细信息
Disjoint NP-pairs are an interesting model of computation with important applications in cryptography and proof complexity. the question whether there exists a complete disjoint NP-pair was posed by Razborov in 1994 and is one of the most important problems in the field. In this paper we prove that there exists a many-one hard disjoint NP-pair which is computed with access to a very weak oracle (a tally NP-oracle).In addition, we exhibit candidates for complete NP-pairs and apply our results to a recent line of research on the construction of hard tautologies from pseudorandom generators.
Computations with sparse matrices are widespread in scientific projects. Used data format affects strongly the performance. Efficient formats for storing sparse matrices are still under development, since the computat...
详细信息
Computations with sparse matrices are widespread in scientific projects. Used data format affects strongly the performance. Efficient formats for storing sparse matrices are still under development, since the computation using widely-used formats (like XY or CSR) is slow and specialized formats (like SPARSITY or CARB) have a large transformation *** this paper, we represent some improvements to the quadtree storage format. We also compare the performance during the execution of some basic routines from the linear algebra using widely-used formats and the quadtree storage format.
Regular hedge languages are an extension of regular tree languages that received renewed attention since their recognition as a formal model of XML schemata. they share several properties with regular languages, but t...
详细信息
Regular hedge languages are an extension of regular tree languages that received renewed attention since their recognition as a formal model of XML schemata. they share several properties with regular languages, but their study is more involved because we need to analyze regularities of sequences of trees instead of words. We show that one shared property is the existence of only finitely many language factors and the possibility to compute and arrange them in a factor matrix with some remarkable properties. We outline an algorithm for the computation of the factor matrix and indicate an application of the factor matrix of an RHL to the solution of a concrete language reconstruction problem.
CIRC is an automated theorem prover based on the circular coinduction principle. the tool is used for the verification of programs, behavioral equivalence checking, and proving properties over infinite data structures...
详细信息
CIRC is an automated theorem prover based on the circular coinduction principle. the tool is used for the verification of programs, behavioral equivalence checking, and proving properties over infinite data structures. In this paper we present two extensions of CIRC that handle the case when the prover indicates an infinite execution for a certain goal. the first extension involves goal simplification rules and a procedure for checking that the new execution is indeed a proof, while the second one refers to finding and proving a generalization of the goal. Each of the extensions is presented based on a case study: Binary Process Algebra (BPA) for checking the proof correctness and Streams for using generalization.
In this paper we introduce a fUML based action language and describe its concrete syntax. the action language uses only elements allowed by the fUML standard for its abstract syntax. the concrete syntax resembles the ...
详细信息
In this paper we introduce a fUML based action language and describe its concrete syntax. the action language uses only elements allowed by the fUML standard for its abstract syntax. the concrete syntax resembles the syntax of existing structured programming languages, with some elements inspired by OCL. the action language is part of the ComDeValCo framework and we are using it to model the functionality of the components, to simulate the execution of the models and to test the models.
Using the machinery of proof orders originally introduced by Bachmair and Dershowitz in the context of canonical equational proofs, we give an abstract, strategy-independent presentation of Groebner basis procedures a...
详细信息
Using the machinery of proof orders originally introduced by Bachmair and Dershowitz in the context of canonical equational proofs, we give an abstract, strategy-independent presentation of Groebner basis procedures and prove the correctness of two classical criteria for recognising superfluous S-polynomials, Buchberger's criteria 1 and 2, w.r.t. arbitrary fair and correct basis construction strategies. To do so, we develop a general method for proving the strategy-independent correctness of superfluous S-polynomial criteria which seems to be quite powerful. We also derive a new superfluous S-polynomial criterion which is a generalisation of Buchberger-1 and is proved to be correct strategy-independently.
In this paper, the problem of finding all zeros of an continuously interval function in a given interval is considered. A new method for solving this problem is proposed. It is based on the idea of isolating the endpo...
详细信息
In this paper, the problem of finding all zeros of an continuously interval function in a given interval is considered. A new method for solving this problem is proposed. It is based on the idea of isolating the endpoints of interval zeros and the technique of interval slopes. We develop the theory of the new method and apply it on a set of smooth functions and a set of nonsmooth functions respectively. In case of smooth functions, We compare the new method to a similar one from [6]. And the numerical results show the efficiency of our new *** case of nonsmooth functions, we can gain the reliable results too. As far as know, the method we proposed is the first one which could solve the nonsmooth interval functions.
the paper describes an algorithm that determines the solutions of a n-dimensional nonlinear equation system within a given interval. the result is based on Semenov algorithm that isolates the solutions and improves up...
详细信息
the paper describes an algorithm that determines the solutions of a n-dimensional nonlinear equation system within a given interval. the result is based on Semenov algorithm that isolates the solutions and improves upon it by introducing Kantorovich existence criterion. In Semenov algorithm the existence of the solution is decided by applying Newton method on each interval containing at most one solution. this article improves and completes the Semenov algorithm by determining the start iteration for each solution. Withthe computed start iteration the Newton method is applied to determine the solution withthe precision e. the Kantorovich error function E(k) is also computed for each iteration k. the paper contains numerical experiments.
暂无评论