Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 17 of 17 for “"Descriptive complexity"”.

  1. Structural techniques in descriptive complexity

    In 2017, Abramsky, Dawar, and Wang published a paper which gave a comonadic characterisation of pebble games, tree-width, and k-variable logic, a key trio of related concepts in Finite Model Theory. In 2018, Abramsky and Shah expanded upon this to give an analogous comonadic characterisation of …

    oxford Repository record for Structural techniques in descriptive complexity (opens in a new tab)

  2. Descriptive Complexity Theory for Constraint Databases

    oxford Restricted access

  3. Counting below #P: Classes, problems and Descriptive Complexity

    Στην παρούσα διπλωματική, μελετάμε μετρητικές κλάσεις οι οποίες περιέχονται στη #P. Μία προσέγγιση, η πιο διαδεδομένη στη Θεωρία Υπολογιστικής Πολυπλοκότητας, είναι ο ορισμός κλάσεων με βάση τη μηχανή Turing. Κλάσεις όπως οι #L, span-L και TotP, #PE προκύπτουν θέτοντας περιορισμούς στους …

    athens Repository record for Counting below #P: Classes, problems and Descriptive Complexity (opens in a new tab)

  4. On the Descriptive Complexity and Ramsey Measure of Sets of Oracles Separating Common Complexity Classes

    … that these classes are all of the same descriptive complexity. Finally we demonstrate that this strengthening of the hypothesis turns it into a sufficient condition for unrelativized relationships, at least in the three cases considered here.

    unt Repository record for On the Descriptive Complexity and Ramsey Measure of Sets of Oracles Separating Common Complexity Classes (opens in a new tab)

  5. On structural and descriptive complexity of hard counting problems the decision version of which is easy

    The complexity class #P introduced by Valiant, contains the counting versions of NP problems. We focus on #PE, the class of #P functions the decision version of which is in P. In fact, we are mostly interested in a subclass of #PE, namely TotP, which contains all self-reducible #PE functions. TotP …

    greece Repository record for On structural and descriptive complexity of hard counting problems the decision version of which is easy (opens in a new tab)

  6. MODEL THEORY AND COMPLEXITY THEORY

    Descriptive complexity theory is a branch of complexity theory that views the hardness of a problem in terms of the complexity of expressing it in some logical formalism; among the resources considered are the number of object variables, quantifier depth, type, and alternation, sentences length …

    maryland Repository record for MODEL THEORY AND COMPLEXITY THEORY (opens in a new tab)

  7. Bounded-curvature motion planning amid polygonal obstacles

    … guarantees and run time analysis in terms of the complexity of the desired solution (see k and λ below). In a sense, our algorithms are output sensitive, which is particularly desirable because there are no known bounds on the solution complexity amid arbitrary polygonal environments. Our first …

    ubc Repository record for Bounded-curvature motion planning amid polygonal obstacles (opens in a new tab) Download PDF for Bounded-curvature motion planning amid polygonal obstacles (opens in a new tab)

  8. Topics on the geometry and classification of Banach lattices

    … 3 and 4) presents various results on the descriptive complexity of classes of Banach lattices and determines the complexity of the lattice isomorphism and isometry equivalence relations. The focus of the third part (Chapter 5) is the construction of a lattice isometrically universal …

    uiuc Repository record for Topics on the geometry and classification of Banach lattices (opens in a new tab)

  9. In pursuit of linear complexity in discrete and computational geometry

    … meshes, and (iii) bounding the expected complexity of weighted Voronoi diagrams. While these topics are broad, here the focus is on identifying structure which implies linear (or near linear) algorithmic and descriptive complexity. The first topic we consider is in geometric optimization. …

    uiuc Repository record for In pursuit of linear complexity in discrete and computational geometry (opens in a new tab)

  10. Some Results for FO-definable Constraint Satisfaction Problems Described by Digraph Homomorphisms

    … constraints. When studying the computational and descriptive complexity of such problems it is convenient to use the equivalent formulation, introduced by Feder and Vardi, that CSPs are homomorphism problems. In this context we ask if there exists a homomorphism to some target structure. Using …

    concordia Download PDF for Some Results for FO-definable Constraint Satisfaction Problems Described by Digraph Homomorphisms (opens in a new tab)

  11. Repeated stressful workplace for a group of clerical workers : complexity, content, and higher-order values of their experiences

    Complexity and content of the stressful workplace, and the goals or expectations of the worker were revealed through a micro-analytic, subjective, and contextual research approach. A content analysis, based on the transactional theory of stress (Lazarus & Folkman, 1984) was used to analyse 1044 …

    ubc Repository record for Repeated stressful workplace for a group of clerical workers : complexity, content, and higher-order values of their experiences (opens in a new tab) Download PDF for Repeated stressful workplace for a group of clerical workers : complexity, content, and higher-order values of their experiences (opens in a new tab)

  12. Descriptive Set Theory and Measure Theory in Locally Compact and Non-locally Compact Groups

    In this thesis we study descriptive-set-theoretic and measure-theoretic properties of Polish groups, with a thematic emphasis on the contrast between groups which are locally compact and those which are not. The work is divided into three major sections. In the first, working jointly with Robert …

    unt Repository record for Descriptive Set Theory and Measure Theory in Locally Compact and Non-locally Compact Groups (opens in a new tab)

  13. An Attempt to Automate <i>NP</i>-Hardness Reductions via <i>SO</i>∃ Logic

    We explore the possibility of automating <i>NP</i>-hardness reductions. We motivate the problem from an artificial intelligence perspective, then propose the use of second-order existential (<i>SO</i>∃) logic as representation language for decision problems. Building upon the theoretical framework …

    waterloo Repository record for An Attempt to Automate <i>NP</i>-Hardness Reductions via <i>SO</i>∃ Logic (opens in a new tab)

  14. On Token Movement Problems

    … This thesis contributes to the computational complexity landscape for these transformation problems. For solution discovery problems where the target property is to form a matching, vertex/edge cut, or shortest path, we show that even though these properties are efficiently computable in the …

    waterloo Repository record for On Token Movement Problems (opens in a new tab)

  15. Gödelovo dílo a jeho význam pro informatiku a filosofii

    Tato práce zkoumá dopad práce Kurta Gödela, zejména jeho vět o neúplnosti, na informatiku. První část se zabývá Gödelovými filozofickými současníky – včetně Russella, Carnapa, Wittgensteina a Tarského – a jejich vlivem na něj samotného, porovnává jeho výsledky s výsledky Alana Turinga a diskutuje …

    brno-tech Repository record for Gödelovo dílo a jeho význam pro informatiku a filosofii (opens in a new tab)