Search results for " Complexity"
showing 10 items of 623 documents
Positive Versions of Polynomial Time
1998
Abstract We show that restricting a number of characterizations of the complexity class P to be positive (in natural ways) results in the same class of (monotone) problems, which we denote by posP . By a well-known result of Razborov, posP is a proper subclass of the class of monotone problems in P . We exhibit complete problems for posP via weak logical reductions, as we do for other logically defined classes of problems. Our work is a continuation of research undertaken by Grigni and Sipser, and subsequently Stewart; indeed, we introduce the notion of a positive deterministic Turing machine and consequently solve a problem posed by Grigni and Sipser.
Noise-tolerant efficient inductive synthesis of regular expressions from good examples
1997
We present an almost linear time method of inductive synthesis restoring simple regular expressions from one representative (good) example. In particular, we consider synthesis of expressions of star-height one, where we allow one union operation under each iteration, and synthesis of expressions without union operations from examples that may contain mistakes. In both cases we provide sufficient conditions defining precisely the class of target expressions and the notion of good examples under which the synthesis algorithm works correctly, and present the proof of correctness. In the case of expressions with unions the proof is based on novel results in the combinatorics of words. A genera…
Efficient learning of regular expressions from good examples
1994
We consider the problem of restoring regular expressions from expressive examples. We define the class of unambiguous regular expressions, the notion of the union number of an expression showing how many union operations can occur directly under any single iteration, and the notion of an expressive example. We present a polynomial time algorithm which tries to restore an unambiguous regular expression from one expressive example. We prove that if the union number of the expression is 0 or 1 and the example is long enough, then the algorithm correctly restores the original expression from one good example. The proof relies on original investigations in theory of covering symbol sequences (wo…
Knot Theory, Jones Polynomial and Quantum Computing
2005
Knot theory emerged in the nineteenth century for needs of physics and chemistry as these needs were understood those days. After that the interest of physicists and chemists was lost for about a century. Nowadays knot theory has made a comeback. Knot theory and other areas of topology are no more considered as abstract areas of classical mathematics remote from anything of practical interest. They have made deep impact on quantum field theory, quantum computation and complexity of computation.
A local complexity based combination method for decision forests trained with high-dimensional data
2012
Accurate machine learning with high-dimensional data is affected by phenomena known as the “curse” of dimensionality. One of the main strategies explored in the last decade to deal with this problem is the use of multi-classifier systems. Several of such approaches are inspired by the Random Subspace Method for the construction of decision forests. Furthermore, other studies rely on estimations of the individual classifiers' competence, to enhance the combination in the multi-classifier and improve the accuracy. We propose a competence estimate which is based on local complexity measurements, to perform a weighted average combination of the decision forest. Experimental results show how thi…
More Support for More-Support
2009
This book provides the most comprehensive account so far of novel and hitherto unexplained factors operative in the choice between synthetic ( prouder ) and analytic ( more proud ) comparatives. It argues that the underlying motivation in using the analytic variant is to mitigate processing demands – a compensatory strategy referred to as more -support. The analytic variant is claimed to be better suited to environments of increased processing complexity – presumably owing to its ability to facilitate early phrase structure recognition, the more transparent one-to-one relation between form and function and possibly because the degree marker more can serve as a structural signal foreshadowin…
Overt and hidden complexity – Two types of complexity and their implications
2014
AbstractLinguistic complexity is the result of the two motivations of explicitness and economy. Most approaches focus on the exlpicitness side of complexity (overt complexity) but there is also an explicitness-oriented side to complexity (hidden complexity). The aim of the paper is to introduce hidden complexity as the neglected side of complexity and to discuss the issues of trade-offs, global complexity and equal complexity from a more encompassing perspective that integrates overt and hidden complexity.
MINIMALIST THEORY OF FICTION AND THE ICTHINKING® METHOD AS A BACKGROUND FOR NEW INSIGHTS TO AUTISM
2021
The standard approach to conceptual understanding in the case of autism uses the distinction of abstract versus concrete thinking. This approach has its benefits but fails to explain all features of language use. For example, some concepts change their meaning in different contexts in contrast to concepts that are more rigid in their uses, such as mathematical concepts. This idea has its background in Minimalist theory of fiction (MTF), a theory that considers ‘skills to use words’ essential for understanding fiction, contrasting with theories that require pretending or make believe to understand fiction. From this background, the theory of Integrative Complexity (IC), and the method animat…
Swarming Models for Facilitating Collaborative Decisions
2010
The paper highlights the computational power of swarming models (i.e., stigmergic mechanisms) to build collaborative support systems for complex cognitive tasks such as facilitation of group decision processes (GDP) in e-meetings. Unlike traditional approaches that minimize the cognitive complexity by incorporating the facilitation knowledge into the system, stigmergic coordination mechanisms minimize the complexity by providing the system with emergent functionalities that are shaped by the environment itself through the possibility to structure it in terms of high-level cognitive artefacts. This is illustrated by conducting a socio-simulation experiment for an envisioned collaborative sof…
Exceptional Configurations of Quantum Walks with Grover’s Coin
2016
We study search by quantum walk on a two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [AKR05]. We show what the most natural coin transformation -- Grover's diffusion transformation -- has a wide class of exceptional configurations of marked locations, for which the probability of finding any of the marked locations does not grow over time. This extends the class of known exceptional configurations; until now the only known such configuration was the "diagonal construction" by [AR08].