Search results for "computability"
showing 10 items of 27 documents
A Novel Border Identification Algorithm Based on an “Anti-Bayesian” Paradigm
2013
Published version of a chapter in the book: Computer Analysis of Images and Patterns. Also available from the publisher at: http://dx.doi.org/10.1007/978-3-642-40261-6_23 Border Identification (BI) algorithms, a subset of Prototype Reduction Schemes (PRS) aim to reduce the number of training vectors so that the reduced set (the border set) contains only those patterns which lie near the border of the classes, and have sufficient information to perform a meaningful classification. However, one can see that the true border patterns (“near” border) are not able to perform the task independently as they are not able to always distinguish the testing samples. Thus, researchers have worked on thi…
On Horn spectra
1991
Abstract A Horn spectrum is a spectrum of a Horn sentence. We show that to solve Asser's problem, and consequently the EXPTIME = ? NEXPTIME question it suffices to consider the class of Horn spectra. We also pose the problem whether or not the generator of every Horn spectrum is a spectrum. We prove that from a negative solution of the generator problem, a negative answer for the EXPTIME = ? NEXPTIME question follows. Some other relations between the generator problem and Asser's problem are given. Finally, the relativized version of the generator problem is formulated and it is shown that it has an affirmative solution for some oracles, and a negative solution for some others.
A new paradigm for pattern classification: Nearest Border Techniques
2013
Published version of a chapter in the book: AI 2013: Advances in Artificial Intelligence. Also available from the publisher at: http://dx.doi.org/10.1007/978-3-319-03680-9_44 There are many paradigms for pattern classification. As opposed to these, this paper introduces a paradigm that has not been reported in the literature earlier, which we shall refer to as the Nearest Border (NB) paradigm. The philosophy for developing such a NB strategy is as follows: Given the training data set for each class, we shall first attempt to create borders for each individual class. After that, we advocate that testing is accomplished by assigning the test sample to the class whose border it lies closest to…
Circuit Lower Bounds via Ehrenfeucht-Fraisse Games
2006
In this paper we prove that the class of functions expressible by first order formulas with only two variables coincides with the class of functions computable by AC/sup 0/ circuits with a linear number of gates. We then investigate the feasibility of using Ehrenfeucht-Fraisse games to prove lower bounds for that class of circuits, as well as for general AC/sup 0/ circuits.
On the decision problem for the guarded fragment with transitivity
2002
The guarded fragment with transitive guards, [GF+TG], is an extension of GF in which certain relations are required to be transitive, transitive predicate letters appear only in guards of the quantifiers and the equality symbol may appear everywhere. We prove that the decision problem for [GF+TG] is decidable. This answers the question posed in (Ganzinger et al., 1999). Moreover, we show that the problem is 2EXPTIME-complete. This result is optimal since the satisfiability problem for GF is 2EXPTIME-complete (Gradel, 1999). We also show that the satisfiability problem for two-variable [GF+TG] is NEXPTIME-hard in contrast to GF with bounded number of variables for which the satisfiability pr…
Structured Frequency Algorithms
2015
B.A. Trakhtenbrot proved that in frequency computability (introduced by G. Rose) it is crucially important whether the frequency exceeds \(\frac{1}{2}\). If it does then only recursive sets are frequency-computable. If the frequency does not exceed \(\frac{1}{2}\) then a continuum of sets is frequency-computable. Similar results for finite automata were proved by E.B. Kinber and H. Austinat et al. We generalize the notion of frequency computability demanding a specific structure for the correct answers. We show that if this structure is described in terms of finite projective planes then even a frequency \(O(\frac{\sqrt{n}}{n})\) ensures recursivity of the computable set. We also show that …
Examining the Quality of Evolution Frameworks and Metamodeling Paradigms of Information Systems Development Methodologies
2011
Information systems development methodologies and associated CASE tools have been considered cornerstones for building quality into an information system. The construction and evaluation of methodologies are usually carried out by evaluation frameworks and metamodels, both considered as meta-methodologies. This chapter investigates and reviews representative metamodels and evaluation frameworks for assessing the capability of methodologies to contribute to high-quality outcomes. It presents a summary of their quality features, strengths, and weaknesses. The chapter ultimately leads to a comparison and discussion of the functional and formal quality properties that traditional meta-methodolo…
Toward computability of trace distance discord
2014
It is known that a reliable geometric quantifier of discord-like correlations can be built by employing the so-called trace distance. This is used to measure how far the state under investigation is from the closest "classical-quantum" one. To date, the explicit calculation of this indicator for two qubits was accomplished only for states such that the reduced density matrix of the measured party is maximally mixed, a class that includes Bell-diagonal states. Here, we first reduce the required optimization for a general two-qubit state to the minimization of an explicit two-variable function. Using this framework, we show next that the minimum can be analytically worked out in a number of r…
A Survey of Continuous-Time Computation Theory
1997
Motivated partly by the resurgence of neural computation research, and partly by advances in device technology, there has been a recent increase of interest in analog, continuous-time computation. However, while special-case algorithms and devices are being developed, relatively little work exists on the general theory of continuous- time models of computation. In this paper, we survey the existing models and results in this area, and point to some of the open research questions. Final Draft peerReviewed
Timed Sets, Functional Complexity, and Computability
2012
AbstractThe construction of various categories of “timed sets” is described in which the timing of maps is considered modulo a “complexity order”. The properties of these categories are developed: under appropriate conditions they form discrete, distributive restriction categories with an iteration. They provide a categorical basis for modeling functional complexity classes and allow the development of computability within these settings. Indeed, by considering “program objects” and the functions they compute, one can obtain models of computability – i.e. Turing categories – in which the total maps belong to specific complexity classes. Two examples of this are introduced in some detail whi…