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.
In [7] it was recently shown that NPℝ ⊆ PCRℝ(poly, O(1)) i.e.the existence of transparent long proofs for NPℝ was established. The latter denotes the class of real number decision problems verifiable in polynomial time as introduced by Blum, Shub and Smale [6]
The problem addressed in this paper is searching for a dependence between the correlation dimension of a time series and the mean square error (MSE) obtained when predicting the future time series values using a multilayer perceptron. The relation between the correlantion dimension and the ability of a neural network to adapt to sample data represented by in-sample mean square error is also studied...
We prove that the one-dimensional sandpile prediction problem is in AC1. The previously best known upper bound on the ACi-scale was AC2. We also prove that it is not in AC1 − − ε for any constant ε> 0.
It is well known that only a few structures can be described up to isomorphism by their elementary theories in the class of all models of fixed cardinality. Unfortunately, most of the natural and interesting structures fail to have this property.
My purpose in this lecture is to explain how the representation of algorithms by recursive programs can be used in complexity theory, especially in the derivation of lower bounds for worst-case time complexity, which apply to all—or, at least, a very large class of—algorithms. It may be argued that recursive programs are not a new computational paradigm, since their manifestation as Herbrand-Gödel-Kleene...
This work concerns representability of arithmetical notions in finite models. It follows the paper by Marcin Mostowski [1], where the notion of FM–representability has been defined. We discuss how far this notion captures the methodological idea of representing infinite sets in finite but potentially infinite domains. We consider mainly some weakenings of the notion of FM–representability....
In this work we focus on a formalisation of the algorithms of lazy exact arithmetic á la Potts and Edalat [1]. We choose the constructive type theory as our formal verification tool. We discuss an extension of the constructive type theory with coinductive types that enables one to formalise and reason about the infinite objects. We show examples of how infinite objects such as streams and expression...
Complexity classes between Grzegorczyk’s E2 and E3 are characterized in terms of provable recursion in a theory EA(I;O) formalising basic principles of Nelson’s Predicative Arithmetic. Extensions by inductive definitions enable full arithmetic PA and higher systems to be recaptured in a setting where the natural bounding functions are “slow” rather than “fast” growing.
We present a domain theoretic framework for obtaining exact solutions of linear boundary value problems. Based on the domain of compact real intervals, we show how to approximate both a fundamental system and a particular solution up to an arbitrary degree of accuracy. The boundary conditions are then satisfied by solving a system of imprecisely given linear equations at every step of the approximation...
Membrane computing is an young but already well developed branch of natural computing, having as its goal to abstract computing models from the structure and the functioning of the living cell. The present paper is an informal introduction to membrane computing, presenting the basic ideas, some central (mathematical) results, and the main areas of application.
Büchi’s problem asked whether a surface of a specific type, defined over the rationals, has integer points other than some known ones. A consequence of a positive answer would be the following strengthening of the negative answer to Hilbert’s tenth problem : the positive existential theory of the rational integers in the language of addition and a predicate for the property ‘x is a square’ would be...
The d-c.e. (difference of c.e.) and dbc (divergence bounded computable) reals are two important subclasses of Δ -reals which have very interesting computability-theoretical as well as very nice analytical properties. Recently, Downey, Wu and Zheng [2] have shown by a double witness technique that not every Δ -Turing degree contains a d-c.e. real. In this paper...
Difficult combinatorial problems typically require exponential time algorithms. Recently there is a new point of view that algorithms operating in (worst-case) exponential time can still be quite useful if the constants in the exponential complexity function are small enough. On the other hand, we do not know many algorithmic design principles for such algorithms up to now. This talk discusses various...
We discuss some known and introduce some new reducibilities on regular sets. We establish some facts on the corresponding degree structures and relate some reducibilities to natural hierarchies of regular sets. As an application, we characterize regular languages whose leaf-language classes (in the balanced model) are contained in the polynomial hierarchy. For any reducibility we try to give some...
Church’s and Turing’s theses dogmatically assert that an informal notion of computability is captured by a particular mathematical concept. I present an analysis of computability that leads to precise concepts, but dispenses with theses.
Two properties of the Co-spectrum of the Joint spectrum of finitely many abstract structures are presented — a Minimal Pair type theorem and the existence of a Quasi-Minimal degree with respect to the Joint spectrum of the structures.
For given real α ∈ {0,1} ∞ , a presentation V of α is a prefix-free and recursively enumerable subset of {0,1}* such that . So, α has a presentation iff α is a left-r.e. real.
We consider copies and constructivizations of structures in admissible sets. In the first section we survey results about copies of countable structures in hereditary finite superstructures and definability (so called syntactical conditions of intrinsically computable properties) and state some conjectures about the uncountable case. The second section is devoted to constructivizations of uncountable...
“Quorum Sensing” has been identified as one of the most consequential microbiology discoveries of the last 10 years. Using Quorum Sensing bacterial colonies synchronize gene expression and phenotype change allowing them, among other things, to protect their niche, coordinate host invasion and bio-film formation. In this contribution we briefly describe the elementary microbiology background and present...
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.