Relevant bibliographies by topics / Descriptive complexity theory

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Books
  4. Book chapters
  5. Conference papers

Academic literature on the topic 'Descriptive complexity theory'

Author: Grafiati
Published: 4 June 2021
Last updated: 18 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Descriptive complexity theory.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Descriptive complexity theory"

1

Sureson, Claude. "Descriptive set theory and Boolean complexity theory." Comptes Rendus de l'Académie des Sciences - Series I - Mathematics 326, no. 2 (January 1998): 255–60. http://dx.doi.org/10.1016/s0764-4442(97)89481-5.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Galambos, Adam. "Descriptive complexity and revealed preference theory." Mathematical Social Sciences 101 (September 2019): 54–64. http://dx.doi.org/10.1016/j.mathsocsci.2019.06.006.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Grohe, Martin. "Finite Variable Logics in Descriptive Complexity Theory." Bulletin of Symbolic Logic 4, no. 4 (December 1998): 345–98. http://dx.doi.org/10.2307/420954.

Full text
Abstract:
Throughout the development of finite model theory, the fragments of first-order logic with only finitely many variables have played a central role. This survey gives an introduction to the theory of finite variable logics and reports on recent progress in the area.For each k ≥ 1 we let Lk be the fragment of first-order logic consisting of all formulas with at most k (free or bound) variables. The logics Lk are the simplest finite-variable logics. Later, we are going to consider infinitary variants and extensions by so-called counting quantifiers.Finite variable logics have mostly been studied on finite structures. Like the whole area of finite model theory, they have interesting model theoretic, complexity theoretic, and combinatorial aspects. For finite structures, first-order logic is often too expressive, since each finite structure can be characterized up to isomorphism by a single first-order sentence, and each class of finite structures that is closed under isomorphism can be characterized by a first-order theory. The finite variable fragments seem to be promising candidates with the right balance between expressive power and weakness for a model theory of finite structures. This may have motivated Poizat [67] to collect some basic model theoretic properties of the Lk. Around the same time Immerman [45] showed that important complexity classes such as polynomial time (PTIME) or polynomial space (PSPACE) can be characterized as collections of all classes of (ordered) finite structures definable by uniform sequences of first-order formulas with a fixed number of variables and varying quantifier-depth.
APA, Harvard, Vancouver, ISO, and other styles
4

Tanaka, Hisao. "Some descriptive-set-theoretical problems in complexity theory." Publications of the Research Institute for Mathematical Sciences 28, no. 4 (1992): 603–14. http://dx.doi.org/10.2977/prims/1195168210.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Bannach, Max, and Till Tantau. "On the Descriptive Complexity of Color Coding." Algorithms 14, no. 3 (March 19, 2021): 96. http://dx.doi.org/10.3390/a14030096.

Full text
Abstract:
Color coding is an algorithmic technique used in parameterized complexity theory to detect “small” structures inside graphs. The idea is to derandomize algorithms that first randomly color a graph and then search for an easily-detectable, small color pattern. We transfer color coding to the world of descriptive complexity theory by characterizing—purely in terms of the syntactic structure of describing formulas—when the powerful second-order quantifiers representing a random coloring can be replaced by equivalent, simple first-order formulas. Building on this result, we identify syntactic properties of first-order quantifiers that can be eliminated from formulas describing parameterized problems. The result applies to many packing and embedding problems, but also to the long path problem. Together with a new result on the parameterized complexity of formula families involving only a fixed number of variables, we get that many problems lie in FPT just because of the way they are commonly described using logical formulas.
APA, Harvard, Vancouver, ISO, and other styles
6

Leivant, Daniel. "Descriptive characterizations of computational complexity." Journal of Computer and System Sciences 39, no. 1 (August 1989): 51–83. http://dx.doi.org/10.1016/0022-0000(89)90019-6.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Saluja, S., K. V. Subrahmanyam, and M. N. Thakur. "Descriptive Complexity of #P Functions." Journal of Computer and System Sciences 50, no. 3 (June 1995): 493–505. http://dx.doi.org/10.1006/jcss.1995.1039.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Debs, Gabriel, Jean Saint Raymond, and Jean Saint Raymond. "The descriptive complexity of connectedness in Polish spaces." Fundamenta Mathematicae 249, no. 3 (2020): 261–86. http://dx.doi.org/10.4064/fm754-7-2019.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Lautemann, Clemens, Pierre McKenzie, Thomas Schwentick, and Heribert Vollmer. "The Descriptive Complexity Approach to LOGCFL." Journal of Computer and System Sciences 62, no. 4 (June 2001): 629–52. http://dx.doi.org/10.1006/jcss.2000.1742.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Cucker, Felipe, and Klaus Meer. "Logics which capture complexity classes over the reals." Journal of Symbolic Logic 64, no. 1 (March 1999): 363–90. http://dx.doi.org/10.2307/2586770.

Full text
Abstract:
AbstractIn this paper we deal with the logical description of complexity classes arising in the real number model of computation introduced by Blum, Shub, and Smale [4]. We adapt the approach of descriptive complexity theory for this model developped in [14] and extend it to capture some further complexity classes over the reals by logical means. Among the latter we find NCℝ, PARℝ, EXPℝ and some others more.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Descriptive complexity theory"

1

Wang, Pengming. "Descriptive complexity of constraint problems." Thesis, University of Cambridge, 2018. https://www.repository.cam.ac.uk/handle/1810/276188.

Full text
Abstract:
Constraint problems are a powerful framework in which many common combinatorial problems can be expressed. Examples include graph colouring problems, Boolean satisfaction, graph cut problems, systems of equations, and many more. One typically distinguishes between constraint satisfaction problems (CSPs), which model strictly decision problems, and so-called valued constraint satisfaction problems (VCSPs), which also include optimisation problems. A key open problem in this field is the long-standing dichotomy conjecture by Feder and Vardi. It claims that CSPs only fall into two categories: Those that are NP-complete, and those that are solvable in polynomial time. This stands in contrast to Ladner's theorem, which, assuming P$\neq$NP, guarantees the existence of problems that are neither NP-complete, nor in P, making CSPs an exceptional class of problems. While the Feder-Vardi conjecture is proven to be true in a number of special cases, it is still open in the general setting. (Recent claims affirming the conjecture are not considered here, as they have not been peer-reviewed yet.) In this thesis, we approach the complexity of constraint problems from a descriptive complexity perspective. Namely, instead of studying the computational resources necessary to solve certain constraint problems, we consider the expressive power necessary to define these problems in a logic. We obtain several results in this direction. For instance, we show that Schaefer's dichotomy result for the case of CSPs over the Boolean domain can be framed as a definability result: Either a CSP is definable in fixed-point logic with rank (FPR), or it is NP-hard. Furthermore, we show that a dichotomy exists also in the general case. For VCSPs over arbitrary domains, we show that a VCSP is either definable in fixed-point logic with counting (FPC), or it is not definable in infinitary logic with counting. We show that these definability dichotomies also have algorithmic implications. In particular, using our results on the definability of VCSPs, we prove a dichotomy on the number of levels in the Lasserre hierarchy necessary to obtain an exact solution: For a finite-valued VCSP, either it is solved by the first level of the hierarchy, or one needs $\Omega(n)$ levels. Finally, we explore how other methods from finite model theory can be useful in the context of constraint problems. We consider pebble games for finite variable logics in this context, and expose new connections between CSPs, pebble games, and homomorphism preservation results.
APA, Harvard, Vancouver, ISO, and other styles
2

Cohen, Michael Patrick. "Descriptive Set Theory and Measure Theory in Locally Compact and Non-locally Compact Groups." Thesis, University of North Texas, 2013. https://digital.library.unt.edu/ark:/67531/metadc271792/.

Full text
Abstract:
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 Kallman, we resolve a conjecture of Gleason regarding the Polish topologization of abstract groups of homeomorphisms. We show that Gleason's conjecture is false, and its conclusion is only true when the hypotheses are considerably strengthened. Along the way we discover a new automatic continuity result for a class of functions which behave like but are distinct from functions of Baire class 1. In the second section we consider the descriptive complexity of those subsets of the permutation group S? which arise naturally from the classical Levy-Steinitz series rearrangement theorem. We show that for any conditionally convergent series of vectors in Euclidean space, the sets of permutations which make the series diverge, and diverge properly, are ?03-complete. In the last section we study the phenomenon of Haar null sets a la Christensen, and the closely related notion of openly Haar null sets. We identify and correct a minor error in the proof of Mycielski that a countable union of Haar null sets in a Polish group is Haar null. We show the openly Haar null ideal may be distinct from the Haar null ideal, which resolves an uncertainty of Solecki. We show that compact sets are always Haar null in S? and in any countable product of locally compact non-compact groups, which extends the domain of a result of Dougherty. We show that any countable product of locally compact non-compact groups decomposes into the disjoint union of a meager set and a Haar null set, which gives a partial positive answer to a question of Darji. We display a translation property in the homeomorphism group Homeo+[0,1] which is impossible in any non-trivial locally compact group. Other related results are peppered throughout.
APA, Harvard, Vancouver, ISO, and other styles
3

Eickmeyer, Kord. "Randomness in complexity theory and logics." Doctoral thesis, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, 2011. http://dx.doi.org/10.18452/16364.

Full text
Abstract:
Die vorliegende Dissertation besteht aus zwei Teilen, deren gemeinsames Thema in der Frage besteht, wie mächtig Zufall als Berechnungsressource ist. Im ersten Teil beschäftigen wir uns mit zufälligen Strukturen, die -- mit hoher Wahrscheinlichkeit -- Eigenschaften haben können, die von Computeralgorithmen genutzt werden können. In zwei konkreten Fällen geben wir bis dahin unbekannte deterministische Konstruktionen solcher Strukturen: Wir derandomisieren eine randomisierte Reduktion von Alekhnovich und Razborov, indem wir bestimmte unbalancierte bipartite Expandergraphen konstruieren, und wir geben eine Reduktion von einem Problem über bipartite Graphen auf das Problem, den minmax-Wert in Dreipersonenspielen zu berechnen. Im zweiten Teil untersuchen wir die Ausdrucksstärke verschiedener Logiken, wenn sie durch zufällige Relationssymbole angereichert werden. Unser Ziel ist es, Techniken aus der deskriptiven Komplexitätstheorie für die Untersuchung randomisierter Komplexitätsklassen nutzbar zu machen, und tatsächlich können wir zeigen, dass unsere randomisierten Logiken randomisierte Komlexitätsklassen einfangen, die in der Komplexitätstheorie untersucht werden. Unter Benutzung starker Ergebnisse über die Logik erster Stufe und die Berechnungsstärke von Schaltkreisen beschränkter Tiefe geben wir sowohl positive als auch negative Derandomisierungsergebnisse für unsere Logiken. Auf der negativen Seite zeigen wir, dass randomisierte erststufige Logik gegenüber normaler erststufiger Logik an Ausdrucksstärke gewinnt, sogar auf Strukturen mit einer eingebauten Additionsrelation. Außerdem ist sie nicht auf geordneten Strukturen in monadischer zweitstufiger Logik enthalten, und auch nicht in infinitärer Zähllogik auf beliebigen Strukturen. Auf der positiven Seite zeigen wir, dass randomisierte erststufige Logik auf Strukturen mit einem unären Vokabular derandomisiert werden kann und auf additiven Strukturen in monadischer Logik zweiter Stufe enthalten ist.
This thesis is comprised of two main parts whose common theme is the question of how powerful randomness as a computational resource is. In the first part we deal with random structures which possess -- with high probability -- properties than can be exploited by computer algorithms. We then give two new deterministic constructions for such structures: We derandomise a randomised reduction due to Alekhnovich and Razborov by constructing certain unbalanced bipartite expander graphs, and we give a reduction from a problem concerning bipartite graphs to the problem of computing the minmax-value in three-player games. In the second part we study the expressive power of various logics when they are enriched by random relation symbols. Our goal is to bridge techniques from descriptive complexity with the study of randomised complexity classes, and indeed we show that our randomised logics do capture complexity classes under study in complexity theory. Using strong results on the expressive power of first-order logic and the computational power of bounded-depth circuits, we give both positive and negative derandomisation results for our logics. On the negative side, we show that randomised first-order logic gains expressive power over standard first-order logic even on structures with a built-in addition relation. Furthermore, it is not contained in monadic second-order logic on ordered structures, nor in infinitary counting logic on arbitrary structures. On the positive side, we show that randomised first-order logic can be derandomised on structures with a unary vocabulary and is contained in monadic second-order logic on additive structures.
APA, Harvard, Vancouver, ISO, and other styles
4

Harwath, Frederik. "On Invariant Formulae of First-Order Logic with Numerical Predicates." Doctoral thesis, Humboldt-Universität zu Berlin, 2018. http://dx.doi.org/10.18452/19609.

Full text
Abstract:
Diese Arbeit untersucht ordnungsinvariante Formeln der Logik erster Stufe (FO) und einiger ihrer Erweiterungen, sowie andere eng verwandte Konzepte der endlichen Modelltheorie. Viele Resultate der endlichen Modelltheorie nehmen an, dass Strukturen mit einer Einbettung ihres Universums in ein Anfangsstück der natürlichen Zahlen ausgestattet sind. Dies erlaubt es, beliebige Relationen (z.B. die lineare Ordnung) und Operationen (z.B. Addition, Multiplikation) von den natürlichen Zahlen auf solche Strukturen zu übertragen. Die resultierenden Relationen auf den endlichen Strukturen werden als numerische Prädikate bezeichnet. Werden numerische Prädikate in Formeln verwendet, beschränkt man sich dabei häufig auf solche Formeln, deren Wahrheitswert auf endlichen Strukturen invariant unter Änderungen der Einbettung der Strukturen ist. Wenn das einzige verwendete numerische Prädikat eine lineare Ordnung ist, spricht man beispielsweise von ordnungsinvarianten Formeln. Die Resultate dieser Arbeit können in drei Teile unterteilt werden. Der erste Teil betrachtet die Lokalitätseigenschaften von FO-Formeln mit Modulo-Zählquantoren, die beliebige numerische Prädikate invariant nutzen. Der zweite Teil betrachtet FO-Sätze, die eine lineare Ordnung samt der zugehörigen Addition auf invariante Weise nutzen, auf endlichen Bäumen. Es wird gezeigt, dass diese dieselben regulären Baumsprachen definieren, wie FO-Sätze ohne numerische Prädikate mit bestimmten Kardinalitätsprädikaten. Für den Beweis wird eine algebraische Charakterisierung der in dieser Logik definierbaren Baumsprachen durch Operationen auf Bäumen entwickelt. Der dritte Teil der Arbeit beschäftigt sich mit der Ausdrucksstärke und der Prägnanz von FO und Erweiterungen von FO auf Klassen von Strukturen beschränkter Baumtiefe.
This thesis studies the concept of order-invariance of formulae of first-order logic (FO) and some of its extensions as well as other closely related concepts from finite model theory. Many results in finite model theory assume that structures are equipped with an embedding of their universe into an initial segment of the natural numbers. This allows to transfer arbitrary relations (e.g. linear order) and operations (e.g. addition, multiplication) on the natural numbers to structures. The arising relations on the structures are called numerical predicates. If formulae use these numerical predicates, it is often desirable to consider only such formulae whose truth value in finite structures is invariant under changes to the embeddings of the structures. If the numerical predicates include only a linear order, such formulae are called order-invariant. We study the effect of the invariant use of different kinds of numerical predicates on the expressive power of FO and extensions thereof. The results of this thesis can be divided into three parts. The first part considers the locality and non-locality properties of formulae of FO with modulo-counting quantifiers which may use arbitrary numerical predicates in an invariant way. The second part considers sentences of FO which may use a linear order and the corresponding addition in an invariant way and obtains a characterisation of the regular finite tree languages which can be defined by such sentences: these are the same tree languages which are definable by FO-sentences without numerical predicates with certain cardinality predicates. For the proof, we obtain a characterisation of the tree languages definable in this logic in terms of algebraic operations on trees. The third part compares the expressive power and the succinctness of different ex- tensions of FO on structures of bounded tree-depth.
APA, Harvard, Vancouver, ISO, and other styles
5

Wood, Joseph Arthur. "Improving software designs via the minimum description length principle." Thesis, University of Sussex, 1998. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.390535.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Schäpers, Uta Katharina Elisabeth. "Nominal versus clausal complexity in spoken and written English theory and description." Frankfurt; M. Berlin Bern Bruxelles New York, NY Oxford Wien Lang, 2007. http://d-nb.info/992431271/04.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

HACHAICHI, YASSINE. "Contributions a la theorie des modeles finis et a la complexite descriptive." Paris 7, 2001. http://www.theses.fr/2001PA077083.

Full text
Abstract:
Ce travail a comme ambition de contribuer a la caracterisation logique de certaines classes de langages, c'est-a-dire a la discipline appelee complexite descriptive. Dans cette these, on donne une caracterisation logique de la classe des langages algebriques non-ambigus, et des caracterisations logiques des langages rudimentaires. Un des interets de ces dernieres caracterisations est le jeu, introduit dans le chapitre 6, qu'elles inspirent. On donnera aussi un resultat utilisant la partie existentielle de ce jeu sur la definissabilite de la connexite des graphes finis dans la continuite des travaux de fagin, de rougemont et schwentick. Dans le chapitre 4, on prouve, par une comparaison de pouvoir d'expression des logiques, que les langages reconnus par des reseaux de petri sont strictement inclus dans ntimen (la classe des langages reconnaissables par une machine de turing non-deterministe en temps lineaire). On utilisera la caracterisation logique des langages des reseaux de petri donnee par parigot et pelz et une caracterisation de ntimen enoncee par lautemann, schwentick et schweikhardt.
APA, Harvard, Vancouver, ISO, and other styles
8

Laubner, Bastian. "The structure of graphs and new logics for the characterization of Polynomial Time." Doctoral thesis, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, 2011. http://dx.doi.org/10.18452/16335.

Full text
Abstract:
Diese Arbeit leistet Beiträge zu drei Gebieten der deskriptiven Komplexitätstheorie. Zunächst adaptieren wir einen repräsentationsinvarianten Graphkanonisierungsalgorithmus mit einfach exponentieller Laufzeit von Corneil und Goldberg (1984) und folgern, dass die Logik "Choiceless Polynomial Time with Counting" auf Strukturen, deren Relationen höchstens Stelligkeit 2 haben, gerade die Polynomialzeit-Eigenschaften (PTIME) von Fragmenten logarithmischer Größe charakterisiert. Der zweite Beitrag untersucht die deskriptive Komplexität von PTIME-Berechnungen auf eingeschränkten Graphklassen. Wir stellen eine neuartige Normalform von Intervallgraphen vor, die sich in Fixpunktlogik mit Zählen (FP+C) definieren lässt, was bedeutet, dass FP+C auf dieser Graphklasse PTIME charakterisiert. Wir adaptieren außerdem unsere Methoden, um einen kanonischen Beschriftungsalgorithmus für Intervallgraphen zu erhalten, der sich mit logarithmischer Platzbeschränkung (LOGSPACE) berechnen lässt. Im dritten Teil der Arbeit beschäftigt uns die ungelöste Frage, ob es eine Logik gibt, die alle Polynomialzeit-Berechnungen charakterisiert. Wir führen eine Reihe von Ranglogiken ein, die die Fähigkeit besitzen, den Rang von Matrizen über Primkörpern zu berechnen. Wir zeigen, dass diese Ergänzung um lineare Algebra robuste Logiken hervor bringt, deren Ausdrucksstärke die von FP+C übertrifft. Außerdem beweisen wir, dass Ranglogiken strikt an Ausdrucksstärke gewinnen, wenn wir die Zahl an Variablen erhöhen, die die betrachteten Matrizen indizieren. Dann bauen wir eine Brücke zur klassischen Komplexitätstheorie, indem wir über geordneten Strukturen eine Reihe von Komplexitätsklassen zwischen LOGSPACE und PTIME durch Ranglogiken charakterisieren. Die Arbeit etabliert die stärkste der Ranglogiken als Kandidat für die Charakterisierung von PTIME und legt nahe, dass Ranglogiken genauer erforscht werden müssen, um weitere Fortschritte im Hinblick auf eine Logik für Polynomialzeit zu erzielen.
This thesis is making contributions to three strands of descriptive complexity theory. First, we adapt a representation-invariant, singly exponential-time graph canonization algorithm of Corneil and Goldberg (1984) and conclude that on structures whose relations are of arity at most 2, the logic "Choiceless Polynomial Time with Counting" precisely characterizes the polynomial-time (PTIME) properties of logarithmic-size fragments. The second contribution investigates the descriptive complexity of PTIME computations on restricted classes of graphs. We present a novel canonical form for the class of interval graphs which is definable in fixed-point logic with counting (FP+C), which shows that FP+C captures PTIME on this graph class. We also adapt our methods to obtain a canonical labeling algorithm for interval graphs which is computable in logarithmic space (LOGSPACE). The final part of this thesis takes aim at the open question whether there exists a logic which generally captures polynomial-time computations. We introduce a variety of rank logics with the ability to compute the ranks of matrices over (finite) prime fields. We argue that this introduction of linear algebra results in robust logics whose expressiveness surpasses that of FP+C. Additionally, we establish that rank logics strictly gain in expressiveness when increasing the number of variables that index the matrices we consider. Then we establish a direct connection to standard complexity theory by showing that in the presence of orders, a variety of complexity classes between LOGSPACE and PTIME can be characterized by suitable rank logics. Our exposition provides evidence that rank logics are a natural object to study and establishes the most expressive of our rank logics as a viable candidate for capturing PTIME, suggesting that rank logics need to be better understood if progress is to be made towards a logic for polynomial time.
APA, Harvard, Vancouver, ISO, and other styles
9

LOESCHER, BERND. "Definissabilite de requetes avec des fonctions une contribution a la theorie de la complexite descriptive." Paris 11, 1997. http://www.theses.fr/1997PA112144.

Full text
Abstract:
1. Nous caracterisons la classe des spectres des formules du premier ordre sur le vocabulaire restreint a un seul symbole de fonction unaire. Par consequent, cette classe est close par complement (reponse partielle aux problemes d'asser et de fagin), et les classes de requetes definissables en logique existentielle du second ordre avec respectivement un et deux quantificateurs sur des fonctions unaires sont separees. 2. Nous analysons le pouvoir d'expression de la logique existentielle monadique du second ordre (np monadique) avec differentes relations predefinies, en particulier une grille carree. Nous pouvons ramener des questions de definissabilite en logique existentielle du second ordre d'arites superieures a des questions equivalentes en np monadique avec une grille carree predefinie. A) nous discutons la question de la definissabilite de la connexite de graphes en np monadique avec une grille carree predefinie. Des consequences inattendues d'une reponse positive sont demontrees. D'autre part, certains resultats ayant jusqu'alors uniquement des preuves considerees comme difficiles sont des consequences d'une reponse negative, en particulier les separations dans la hierarchie de m. Ajtai. B) nous etudions la question d'une separation des classes de requetes definissables en logique existentielle du second ordre avec quantification sur des fonctions unaires et de np monadique sur des grilles carrees colorees. Nous montrons que cette separation implique l'existence d'une np-propriete de graphes qui n'est pas definissable en quantifiant sur une seule relation binaire (une vieille question ouverte posee par r. Fagin). En particulier, l'existence d'une propriete d'ensembles carres colores qui est definissable avec quantification sur des fonctions unaires, mais pas avec seulement deux fonctions, implique une reponse a la question de r. Fagin.
APA, Harvard, Vancouver, ISO, and other styles
10

Nijjar, Paul. "An Attempt to Automate NP-Hardness Reductions via SO∃ Logic." Thesis, University of Waterloo, 2004. http://hdl.handle.net/10012/1162.

Full text
Abstract:
We explore the possibility of automating NP-hardness reductions. We motivate the problem from an artificial intelligence perspective, then propose the use of second-order existential (SO∃) logic as representation language for decision problems. Building upon the theoretical framework of J. Antonio Medina, we explore the possibility of implementing seven syntactic operators. Each operator transforms SO∃ sentences in a way that preserves NP-completeness. We subsequently propose a program which implements these operators. We discuss a number of theoretical and practical barriers to this task. We prove that determining whether two SO∃ sentences are equivalent is as hard as GRAPH ISOMORPHISM, and prove that determining whether an arbitrary SO∃ sentence represents an NP-complete problem is undecidable.
APA, Harvard, Vancouver, ISO, and other styles

Books on the topic "Descriptive complexity theory"

1

Immerman, Neil. Descriptive Complexity. New York, NY: Springer New York, 1999.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
2

Nominal versus clausal complexity in spoken and written English: Theory and description. Frankfurt am Main: Peter Lang, 2009.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
3

Grohe, Martin. Descriptive Complexity, Canonisation, and Definable Graph Structure Theory. Cambridge University Press, 2017.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
4

Skrzypczak, Michał. Descriptive Set Theoretic Methods in Automata Theory: Decidability and Topological Complexity. Springer, 2016.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
5

1953-, Immerman Neil, Kolaitis Phokion, and DIMACS Workshop on Descriptive Complexity and Finite Models (1996 : Princeton University), eds. Descriptive complexity and finite models: Proceedings of a DIMACS workshop, January 14-17, 1996, Princeton University. Providence, R.I: American Mathematical Society, 1997.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
6

Pawlak, Nina, and Izabela Will, eds. West African languages. Linguistic theory and communication. University of Warsaw Press, 2020. http://dx.doi.org/10.31338/uw.9788323546313.

Full text
Abstract:
The monograph covers the main aspects of studies on West African languages related to the diversity of structural patterns and complexity of their linguistic assignment. It includes various topics ranging from linguistic description and conceptualization patterns to the sociolinguistics of contemporary refugee camps. Typological diversity is enriched with the presentation of pidgin structures and sign languages. Structural differences between languages are seen from a comparative perspective, which also indicates the areal dimension of linguistic processes. The presentations of linguists from both Europe and Africa develop the idea of convergence area in West Africa, which is motivated by the contact between languages of different affiliations to language families and common cultural basis of language development.
APA, Harvard, Vancouver, ISO, and other styles
7

James, Elaine T. The Map of the Body. Oxford University Press, 2017. http://dx.doi.org/10.1093/acprof:oso/9780190619015.003.0005.

Full text
Abstract:
The descriptive poems of the Song (sometimes called waṣfs) are three long texts that punctuate and lend a sense of overall structure to the Song. In these poems, the lover’s body is described as a landscape. This chapter offers a reading of these three texts together as a conceit of process. It argues that the landscape concept relies on an intuition of perspective—of viewing—that orders the audience’s response to the poem’s subject. The descriptive poems build a progressively more developed vision of the lover’s body as a map. As they do so, they model a way of seeing—a lover’s vision—that sees with increasing complexity over time.
APA, Harvard, Vancouver, ISO, and other styles
8

Succi, Sauro. Generalized Hydrodynamics Beyond Navier–Stokes. Oxford University Press, 2018. http://dx.doi.org/10.1093/oso/9780199592357.003.0006.

Full text
Abstract:
The work of Chapman and Enskog opened a long period, lasting about three decades, in which most of the activity in kinetic theory was directed to the computation of the transport coefficients for different types of intermolecular potentials. Seeking the solution of the full Boltzmann equation itself was not much in focus, mostly on account of its daunting complexity. This situation took a sharp turn in 1949, with the publication of Harold Grad’s thesis. This Chapter presents the derivation of generalized hydrodynamics beyond the realm of the Navier-Stokes description, with special reference to Grad’s thirteen-moment formulation.
APA, Harvard, Vancouver, ISO, and other styles
9

Norcross, John C., and Marvin R. Goldfried, eds. Handbook of Psychotherapy Integration. Oxford University Press, 2019. http://dx.doi.org/10.1093/med-psych/9780190690465.001.0001.

Full text
Abstract:
Psychotherapists have come to realize that, given the complexity of human behavior, no single theory or treatment can ever suffice for all patients, disorders, and situations. The ideological Cold War has abated as clinicians look across single-school approaches to see what can be learned—and how patients can benefit—from alternative orientations. Integrative now constitutes the most frequent orientation of mental health professionals. This volume provides a comprehensive state-of-the-art description of psychotherapy integration by leading proponents. Replete with clinical vignettes, this unique handbook will prove invaluable to practitioners, students, and researchers alike.
APA, Harvard, Vancouver, ISO, and other styles
10

Foley, Richard. Related Topics. Oxford University Press, 2018. http://dx.doi.org/10.1093/oso/9780190865122.003.0004.

Full text
Abstract:
This chapter examines Wittgenstein’s critique of philosophy’s premium on simplicity and generality. Although philosophy overlaps with the sciences, it also leans toward the humanities in the open-ended character of its core issues. Additionally, the author discusses Alasdair MacIntyre’s and Jean-Paul Sartre’s different views on the appeal of stories, and discusses as well how the insights of stories have the same features as those of the humanities in being indexical, prescriptive, and perspectival. The social sciences occupy a midpoint between the natural sciences and humanities, aiming to be descriptive, with high value on collective knowledge. But because they deal with human societies, there are constraints on efforts to minimize indexicality. And, because many issues about human societies cannot be addressed without understanding the viewpoints of individuals in the societies, there are also challenges in minimizing perspectivality and complexity.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Book chapters on the topic "Descriptive complexity theory"

1

Ebbinghaus, Heinz-Dieter, and Jörg Flum. "Descriptive Complexity Theory." In Advances in Comparative and Environmental Physiology, 119–63. Berlin, Heidelberg: Springer Berlin Heidelberg, 1995. http://dx.doi.org/10.1007/978-3-662-03182-7_7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Ebbinghaus, Heinz-Dieter, and Jörg Flum. "Descriptive Complexity Theory." In Springer Monographs in Mathematics, 119–64. Berlin, Heidelberg: Springer Berlin Heidelberg, 1995. http://dx.doi.org/10.1007/3-540-28788-4_7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Immerman, Neil. "Descriptive and computational complexity." In Fundamentals of Computation Theory, 244–45. Berlin, Heidelberg: Springer Berlin Heidelberg, 1989. http://dx.doi.org/10.1007/3-540-51498-8_23.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Vianu, Victor. "Databases and finite-model theory." In Descriptive Complexity and Finite Models, 97–148. Providence, Rhode Island: American Mathematical Society, 1997. http://dx.doi.org/10.1090/dimacs/031/04.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Korovina, Margarita, and Oleg Kudinov. "On Higher Effective Descriptive Set Theory." In Unveiling Dynamics and Complexity, 282–91. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-58741-7_27.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Skrzypczak, Michał. "Descriptive Complexity of mso+u." In Descriptive Set Theoretic Methods in Automata Theory, 159–71. Berlin, Heidelberg: Springer Berlin Heidelberg, 2016. http://dx.doi.org/10.1007/978-3-662-52947-8_9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Grädel, Erich, and Stephan Kreutzer. "Descriptive Complexity Theory for Constraint Databases." In Computer Science Logic, 67–81. Berlin, Heidelberg: Springer Berlin Heidelberg, 1999. http://dx.doi.org/10.1007/3-540-48168-0_6.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Schöning, Uwe, and Randall Pruim. "Spectral Problems and Descriptive Complexity Theory." In Gems of Theoretical Computer Science, 61–70. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/978-3-642-60322-8_8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Cadilhac, Michaël, Andreas Krebs, and Klaus-Jörn Lange. "A Language-Theoretical Approach to Descriptive Complexity." In Developments in Language Theory, 64–76. Berlin, Heidelberg: Springer Berlin Heidelberg, 2016. http://dx.doi.org/10.1007/978-3-662-53132-7_6.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Eickmeyer, Kord, and Martin Grohe. "Randomisation and Derandomisation in Descriptive Complexity Theory." In Computer Science Logic, 275–89. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-15205-4_23.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Descriptive complexity theory"

1

Grädel, Erich, and Klaus Meer. "Descriptive complexity theory over the real numbers." In the twenty-seventh annual ACM symposium. New York, New York, USA: ACM Press, 1995. http://dx.doi.org/10.1145/225058.225151.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Cozman, Fabio Gagliardi, and Denis Deratani Mauá. "The Finite Model Theory of Bayesian Networks: Descriptive Complexity." In Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. California: International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/727.

Full text
Abstract:
We adapt the theory of descriptive complexity to Bayesian networks, to quantify the expressivity of specifications based on predicates and quantifiers. We show that Bayesian network specifications that employ first-order quantification capture the complexity class PP; by allowing quantification over predicates, the resulting Bayesian network specifications capture each class in the hierarchy PP^(NP^...^NP), a result that does not seem to have equivalent in the literature.
APA, Harvard, Vancouver, ISO, and other styles
3

Cha, Jianzhong, and Wei Guo. "The Methodology and Environment for Modeling and Implementation in Concurrent Engineering." In ASME 1993 Design Technical Conferences. American Society of Mechanical Engineers, 1993. http://dx.doi.org/10.1115/detc1993-0292.

Full text
Abstract:
Abstract The Concurrent Design, characterized with the integration of a large scale information and knowledge environment in a Computer Integrated Manufacturing System (CIMS), will involve multidiscipline and multidomain of knowledge. This will lead to the difficulty to implement the concurrent design with the nature of complexity, integrality and systematicity in design process, which caused by the above mentioned knowledge integration. This paper, based on the fundamental theory of design processes and adopted the knowledge processing theory and techniques offered by Intelligence Engineering, has investigated: the descriptive models which represent the general framework of concurrent design processes; the cognitive models that highlights the reasoning aspect performed by group of human experts from multidisciplines in concurrent design process; the prescriptive model which is prepared for being used in an computerized automated concurrent design system; the computable model represented with the object-oriented method, which can be executed in the computer world for automated concurrent design. Also this paper developed an engineering environment of analyzing, modeling and implementing with an architecture of Integrated Intelligent Unit, borrowed from the theory of Intelligence Engineering. In a separate paper, the authors apply the above methodology to a concrete concurrent design on a mechanical system to show the feasibility and advantages of the proposed method.
APA, Harvard, Vancouver, ISO, and other styles
4

Jacobus, Frank, and Marc Manack. "Remote Control: The Natural Language of Architecture." In 2018 ACSA International Conference. ACSA Press, 2018. http://dx.doi.org/10.35483/acsa.intl.2018.30.

Full text
Abstract:
The architectural design process is a means of translating information into form, and has long relied on indirect (“remote”) control mechanisms for communicating and translating the architect’s authorial intent into a built work. These methods have generally evolved from a more direct, physical basis, as both technology and the discipline have evolved. To communicate design ideas, architects have relied on methodologies that range from an extreme desire for control, to models that attempt to relinquish many controls entirely. Early communication models, in part due to lack of material, form, and program diversity, allowed for a less systematic and complex descriptive method; inscriptions in the earth, physical detail models along with a set of instructions, or simple scale models of the intention were all that was required.2 As cultures and their technologies advanced, communication methods such as scaled orthographic drawings, specifications and other forms of written instructions, and now fully realized Building Information Models, have become normative practice in a profession that looks for total control of the built work before it is physically realized. Apart from the communicative control models mentioned above, there are authorial models which have also progressed in complexity and abstraction alongside societal advancements. In the discipline’s infancy, authorship involved subtle evolutions of proportion and order within a well-established typological system. In modernism, the authorial models evolved as architects experimented with increased typological invention in response to a radically changing technological and social environment. Advancing to the contemporary “digital” moment, architects continue to develop systems to control complexities within the work, mapping strategies that deal with collecting and spatializing data, while others see contemporary design tools as a means to relinquish some design control to outside forces whose unexpected potential is compelling. This paper gives examples of remote communicative and authorial controls, and posits a new theory of the potential meaningful effects of leveraging these control mechanisms in new ways using three projects by SILO AR+D.
APA, Harvard, Vancouver, ISO, and other styles
5

Bonatti, Piero, Marco Faella, Iliana M. Petrova, and Luigi Sauro. "A New Semantics for Overriding in Description Logics (Extended Abstract)." In Twenty-Sixth International Joint Conference on Artificial Intelligence. California: International Joint Conferences on Artificial Intelligence Organization, 2017. http://dx.doi.org/10.24963/ijcai.2017/705.

Full text
Abstract:
Nonmonotonic inferences are not yet supported by Description Logic technology, although their potential usefulness is widely recognized. Lack of support to nonmonotonic reasoning is due to a number of issues related to expressiveness, computational complexity, and optimizations. This work contributes to the practical support of nonmonotonic reasoning in description logics by introducing a new semantics designed to address knowledge engineering needs. The formalism is validated through extensive comparison with the other nonmonotonic DLs, and systematic scalability tests.
APA, Harvard, Vancouver, ISO, and other styles
6

Eckert, Claudia, John Clarkson, and Chris Earl. "Predictabilty of Change in Engineering: A Complexity View." In ASME 2005 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. ASMEDC, 2005. http://dx.doi.org/10.1115/detc2005-85435.

Full text
Abstract:
Design changes can be surprisingly complex. We examine the problems they cause and discuss the problems involved in predicting how changes propagate, based on empirical studies. To assist this analysis we distinguish between (a) a static background of connectivities (b) descriptions of designs, processes, resources and requirements and (c) the dynamics of design tasks acting on descriptions. The background might consist of existing designs and subsystems, or established processes used to create them. The predictability of design change is examined in terms of this model, especially the types and scope of uncertainties and where complexities arise. An industrial example of change propagation is presented in terms of the background (connectivity) - description - action model.
APA, Harvard, Vancouver, ISO, and other styles
7

Gao, Z., R. V. R. Pandya, B. Shotorban, and F. Mashayek. "Current Issues in Analytical Description of Particle/Droplet-Laden Turbulent Flows." In ASME/JSME 2003 4th Joint Fluids Summer Engineering Conference. ASMEDC, 2003. http://dx.doi.org/10.1115/fedsm2003-45668.

Full text
Abstract:
The particle/droplet-laden turbulent flows occur in many important natural and technological situations, e.g., cloud [1], aerosol transport and deposition [2], spray combustion [3, 4], fluidized bed combustion [5], plasma spray coating and synthesis of nanoparticles [6]. Undoubtedly, turbulence itself remains as a difficult and unsolved problem of classical mechanics despite many persistent efforts by physicists and engineers. The presence of particles/droplets (hereafter simply referred to as particles) further adds to the complexity of the turbulence. The particle behavior in turbulent flows gives rise to many interesting phenomena, such as, turbophoresis [7], turbulent thermal diffusion and barodiffusion [8, 9], preferential distribution, and anomaly and intermittency [9, 10]. It is challenging to come up with a unique predictive theory for the particle phase which is useful for engineering purposes and also capable in quantifying various related phenomena.
APA, Harvard, Vancouver, ISO, and other styles
8

Gutiérrez-Basulto, Víctor, Jean Christoph Jung, and Leif Sabellek. "Reverse Engineering Queries in Ontology-Enriched Systems: The Case of Expressive Horn Description Logic Ontologies." In Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. California: International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/255.

Full text
Abstract:
We introduce the query-by-example (QBE) paradigm for query answering in the presence of ontologies. Intuitively, QBE permits non-expert users to explore the data by providing examples of the information they (do not) want, which the system then generalizes into a query. Formally, we study the following question: given a knowledge base and sets of positive and negative examples, is there a query that returns all positive but none of the negative examples? We focus on description logic knowledge bases with ontologies formulated in Horn-ALCI and (unions of) conjunctive queries. Our main contributions are characterizations, algorithms and tight complexity bounds for QBE.
APA, Harvard, Vancouver, ISO, and other styles
9

Lutz, Carsten, and Leif Sabellek. "Ontology-Mediated Querying with the Description Logic EL: Trichotomy and Linear Datalog Rewritability." In Twenty-Sixth International Joint Conference on Artificial Intelligence. California: International Joint Conferences on Artificial Intelligence Organization, 2017. http://dx.doi.org/10.24963/ijcai.2017/164.

Full text
Abstract:
We consider ontology-mediated queries (OMQs) based on an EL ontology and an atomic query (AQ), provide an ultimately fine-grained analysis of data complexity and study rewritability into linear Datalog-aiming to capture linear recursion in SQL. Our main results are that every such OMQ is in AC0, NL-complete or PTime-complete, and that containment in NL coincides with rewritability into linear Datalog (whereas containment in AC0 coincides with rewritability into first-order logic). We establish natural characterizations of the three cases, show that deciding linear Datalog rewritability (as well as the mentioned complexities) is ExpTime-complete, give a way to construct linear Datalog rewritings when they exist, and prove that there is no constant bound on the arity of IDB relations in linear Datalog rewritings.
APA, Harvard, Vancouver, ISO, and other styles
10

Bednarczyk, Bartosz, Stephane Demri, and Alessio Mansutti. "A Framework for Reasoning about Dynamic Axioms in Description Logics." In Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}. California: International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/ijcai.2020/233.

Full text
Abstract:
Description logics are well-known logical formalisms for knowledge representation. We propose to enrich knowledge bases (KBs) with dynamic axioms that specify how the satisfaction of statements from the KBs evolves when the interpretation is decomposed or recomposed, providing a natural means to predict the evolution of interpretations. Our dynamic axioms borrow logical connectives from separation logics, well-known specification languages to verify programs with dynamic data structures. In the paper, we focus on ALC and EL augmented with dynamic axioms, or to their subclass of positive dynamic axioms. The knowledge base consistency problem in the presence of dynamic axioms is investigated, leading to interesting complexity results, among which the problem for EL with positive dynamic axioms is tractable, whereas EL with dynamic axioms is undecidable.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Descriptive complexity theory' for particular source types:
Journal articles Books
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography