The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
This procedure for strengthening correctness to correctness relative to small changes in any interesting parameters can be extended to apply to any hybrid systems language, with slight changes in primitive relations. The key idea is that the physical systems are dynamical systems equipped with topologies on state spaces, that finite automata have to work relative to finite space quotient topologies,...
Pure type systems feature domain-specified λ-abstractions λx:A.M. We present a variant of pure type systems, which we call domain-free pure type systems, with domain-free λ-abstractions λx.M. We study the basic properties of domain-free pure type systems and establish their formal relationship with pure type systems.
We consider relational databases organized over an ordered domain with some additional relations—a typical example is the ordered domain of rational numbers together with the ternary relation + of addition. In the focus of our study are the first order (FO) queries that are invariant under order-preserving “permutations” — such queries are called order-generic. It has recently been discovered that...
This paper introduces an approach to defining and computing distances between programs via continuous generalized distance functions ρ: A×A→D, where A and D are directed complete partial orders with the induced Scott topology, A is a semantic domain, and D is a domain representing distances (usually, some version of interval numbers). A continuous distance function ρ can define a To topology...
Using a function algebra characterization of exponential time due to Monien [5], in the style of Bellantoni-Cook [2], we characterize exponential time functions of linear growth via a safe course-of-values recursion scheme.
This paper studies the complexity of the query answering problem in logic databases with complex values. Logic databases are represented as Horn clause logic programs; complex values are described in a data model based on equational theories. As examples of complex values, we consider trees, bags and finite sets. We give a natural sufficient condition under which the query answering problem for non-recursive...
A new concept is introduced of globally stable behavior of a deductive data base reacting to stimuli of its active medium. Various problems of integrity constraints restoration after updates fit this general frame. We explore the computational complexity of the problem of stability of a deductive data base in a given DB state with respect to its medium.
The provability problem for the Horn fragment of linear logic is NP-complete [4, 1]. In this work we investigate various definitions of concurrency proposed in [2] and establish the complexity of the provability problem and the problem of concurrency recognition. The notion of k-maximal concurrency is introduced which guarantees polynomial time provability. Theorems on hierarchy and on complexity...
This paper was inspired by [FBW 94]. An arbitrary upper bound on the size of some program for the target function suffices for the learning of some program for this function. In [FBW 94] it was discovered that if “learning” is understood as “identification in the limit,” then in some programming languages it is possible to learn a program of size not exceeding the bound, while in some other programming...
The cut-elimination technique is well developed for classical higher order systems, but, since the normal form (not normalization) theorem was established by Mints[1, 2, 3, 4, 5], not much further progress has been achieved for the logical systems with an ε-symbol. We give a cut elimination procedure for the second order propositional logic with Hilbert's ε-symbol, extensionality and full comprehension...
We study bimodal logic system S52C having two modal operators □0 and □1, each of which satisfies the axioms of S5 and in addition, an axiom for commutability of modal operators: □0□1p]≡□1□0p. The main result of this paper establishes that the bimodal logic S52C and all its extensions have finite bases for admissible inference rules. We also show that even...
In computer science, one is interested mainly in finite objects. Insofar as infinite objects are of interest, they must be computable, i.e., recursive, thus admitting an effective finite representation. This leads to the notion of a recursive graph, or, more generally, a recursive structure, model or data base. We summarize our recent work on recursive structures and data bases, including (i) high...
Many logics used in computer science have an intractable satisfiability (model-checking, derivability) problem. This restricts their general applicability severely. May be restricting to smaller classes of admissible formulas can bring down the complexity bounds. In the present paper we follow this strategy for the subset space logic proposed by Moss and Parikh recently [Moss and Parikh 1992], [Dabrowski...
Quantifier-free prepositional linear affine logic (i.e. linear logic with weakening) is decidable [Kop, Laf2]. Lafont and Scedrov proved that the multiplicative fragment of second-order linear logic is undecidable [LS]. In this paper we show that second order linear affine logic is undecidable as well. At the same time it turns out that even its multiplicative fragment is undecidable. Moreover, we...
The extended operational (term-labeled modal) language is used to give the axiomatic description for functional proof predicate supplied with effective operations on proofs induced by modus ponens and necessitation rules. An additional operation is involved which restores a statement from its proof. The arithmetical completeness and decidability theorems are proved. The cut-elimination property for...
In this article we introduce the functions $${}^{Fi}(x_1 ,x_2 )^{\lambda _1 ,...,\lambda _3 }$$ and $${}^{Th}(x_1 ,x_2 ,x_3 )^{\lambda _1 ,...,\lambda _{2^3 } }$$ (i=1,2,3), of the word variables xi and of the natural number variables λi, where s ≥ 0. By means of these functions, we give exactly the general solution...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.