Relatively Quantified Constraint Satisfaction (2009)
Manuel Bodirsky, École Polytechnique, Hubie Chen
The constraint satisfaction problem (CSP) is a convenient framework for modelling search problems; the CSP involves deciding, given a set of constraints on variables, whether or not there is an...
On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction (2009)
Bodirsky, Manuel, Hils, Martin, Martin, Barnaby
The universal-algebraic approach has proved a powerful tool in the study of the computational complexity of constraint satisfaction problems (CSPs). This approach has previously been applied to the...
aleph_0-categorical Structures: Endomorphisms and Interpretations (2009)
Bodirsky, Manuel, Junker, Markus
We extend the Ahlbrandt--Ziegler analysis of interpretability in aleph_0-categorical structures by showing that existential interpretation is controlled by the monoid of self--embeddings and positive...
All reducts of the random graph are model-complete (2009)
Bodirsky, Manuel, Pinsker, Michael
We study locally closed transformation monoids which contain the automorphism group of the random graph. We show that such a transformation monoid is locally generated by the permutations in the...
Im Fach Informatik, Manuel Bodirsky, Prof Dr, Jürgen Mlynek, Dekan Mathematisch-naturwissenschaftlichen, Fakultät Ii, ...
eingereicht an der Mathematisch-Naturwissenschaftlichen Fakultät II der Humboldt-Universität zu Berlin von Dipl.-Inf.
Locally Consistent Constraint Satisfaction Problems (2009)
An instance of a constraint satisfaction problem (CSP) is variable k-consistent if any subinstance with at most k variables has a solution. For a fixed constraint language L, ρk(L) is the largest...
The reducts of equality up to primitive positive interdefinability (2008)
Bodirsky, Manuel, Chen, Hubie, Pinsker, Michael
We initiate the study of reducts of relational structures up to primitive positive interdefinability: After providing the tools for such a study, we apply these tools in order to obtain a...
Datalog and Constraint Satisfaction with Infinite Templates (2008)
Bodirsky, Manuel, Dalmau, Victor
On finite structures, there is a well-known connection between the expressive power of Datalog, finite variable logics, the existential pebble game, and bounded hypertree duality. We study this...
This paper studies peek arc consistency, a reasoning technique that extends the well-known arc consistency technique for constraint satisfaction. In contrast to other more costly extensions of arc...
Collapsibility in Infinite-Domain Quantified (2008)
Manuel Bodirsky, Hubie Chen, Departament De Tecnologia
Abstract. In this article, we study the quantified constraint satisfaction problem (QCSP) over infinite domains. We develop a technique called collapsibility that allows one to give strong complexity...
A Fast Algorithm and Lower Bound for Temporal Reasoning (2008)
We introduce a new tractable temporal constraint language, which strictly contains the Ord-Horn language of Buerkert and Nebel and the class of AND/OR precedence constraints. The algorithm we present...
A fast algorithm and lower bound for temporal reasoning (2008)
Abstract. We introduce two new tractable temporal constraint languages, which both strictly contain the Ord-Horn language of Bürkert and Nebel. The algorithm we present for these languages decides...
A fast algorithm and lower bound for temporal reasoning (2008)
We introduce two new tractable temporal constraint languages, which both strictly contain the class Ord-Horn of Bürkert and Nebel. The presented algorithms decide whether a given set of constraints...
Manuel Bodirsky, Clemens Gröpl, Daniel Johannsen, Mihyun Kang
ABSTRACT. We present a decomposition strategy for c-nets, i. e., rooted 3-connected planar maps. The decomposition yields an algebraic equation for the number of c-nets with a given number of...
Sampling unlabeled biconnected planar graphs (2008)
Manuel Bodirsky, Clemens Gröpl, Mihyun Kang
Abstract. We present an expected polynomial time algorithm to generate a 2-connected unlabeled planar graph uniformly at random. To do this we first derive recurrence formulas to count the exact...
Collapsibility in Infinite-Domain Quantified Constraint Satisfaction (2008)
Manuel Bodirsky, Hubie Chen, Departament De Tecnologia
Abstract. In this article, we study the quantified constraint satisfaction problem (QCSP) over infinite domains. We develop a technique called collapsibility that allows one to give strong complexity...
Collapsibility in Infinite-Domain Quantified (2008)
Manuel Bodirsky, Hubie Chen, Departament De Tecnologia
Abstract. In this article, we study the quantified constraint satisfaction problem (QCSP) over infinite domains. We develop a technique called collapsibility that allows one to give strong complexity...
Determining the consistency of partial tree descriptions (2008)
Abstract. We present an efficient algorithm that checks the consistency of partial descriptions of ordered trees. The constraint language of these descriptions was introduced by Cornell in...
Determining the consistency of partial tree descriptions (2008)
Abstract. We present an efficient algorithm that checks the consistency of partial descriptions of ordered trees. The constraint language of these descriptions was introduced by Cornell in...
Determining the Consistency of (2008)
Partial Tree Descriptions, Manuel Bodirsky, Martin Kutz
We present an e#cient algorithm that checks the consistency of partial descriptions of ordered trees. The constraint language of these descriptions was introduced by Cornell in computational...
Constraint satisfaction problems with infinite templates (2008)
Abstract. Allowing templates with infinite domains greatly expands the range of problems that can be formulated as a non-uniform constraint satisfaction problem. It turns out that many CSPs over...
Non-dichotomies in constraint satisfaction complexity (2008)
Abstract. We show that every computational decision problem is polynomialtime equivalent to a constraint satisfaction problem (CSP) with an infinite template. We also construct for every decision...
Programming Systems Lab (2007)
Manuel Bodirsky, Katrin Erk, Alexander Koller, Joachim Niehren
www.ps.uni-sb.de/~{bodirsky,erk,koller,niehren} Abstract. The constraint language for lambda structures (CLLS) can model lambda terms that are known only partially. In this paper, we introduce beta...
Manuel Bodirsky, Denys Duchier, Joachim Niehren
Abstract. Dominance constraints are logical descriptions of trees that have numerous applications in computational linguistics. Ecient algorithms for the subclass of normal dominance constraints were...
Long-run Properties of Periodic Probabilistic Systems (2007)
Manuel Bodirsky, Manuel Bodirsky, Timo Von Oertzen, Fachrichtung Informatik
Universitat des Saarlandes Abstract. Partially-observable Markov chains (POMs) are a fundamental tool for modelling probabilistic systems. We are interested in the algorithmic complexity of checking...
Track 1: Algorithms, Complexity and Models of Computation. Eciently Dealing with Periods (2007)
Manuel Bodirsky, Timo Von Oertzen, Fachrichtung Informatik
Universitat des Saarlandes In nite sequences where the elements repeat themselves periodically naturally occur in many areas of theoretical computer science, from learning theory to convergence...
Abstract. We present an ecient algorithm that checks the satisability of pure dominance constraints, which is a tree description language contained in several constraint languages studied in...
Qualitative temporal and spatial reasoning revisited (2007)
Abstract. Establishing local consistency is one of the main algorithmic techniques in temporal and spatial reasoning. In this area, one of the central questions for the various proposed temporal and...
Quantified equality constraints (2007)
An equality template (also equality constraint language) is a relational structure with infinite universe whose relations can be defined by boolean combinations of equalities. We prove a complete...
Qualitative temporal and spatial reasoning revisited (2007)
Abstract. Establishing local consistency is one of the main algorithmic techniques in temporal and spatial reasoning. A central question for the various proposed temporal and spatial constraint...
Qualitative temporal and spatial reasoning revisited (2007)
Abstract. Establishing local consistency is one of the main algorithmic techniques in temporal and spatial reasoning. A central question for the various proposed temporal and spatial constraint...
Enumeration and Asymptotic Properties of Unlabeled Outerplanar Graphs, in "Electronic (2007)
Manuel Bodirsky, Éric Fusy, Mihyun Kang, Stefan Vigerske, Projet Algo, Inria Rocquencourt
We determine the exact and asymptotic number of unlabeled outerplanar graphs. The exact number gn of unlabeled outerplanar graphs on n vertices can be computed in polynomial time, and gn is...
Maximal infinite-valued constraint languages (2007)
We generalize the notion of maximal constraint languages from finite to infinite domains. If the constraint language can be defined with an ω-categorical structure, then maximal constraint languages...
Manuel Bodirsky, Hubie Chen, Jan Kára, Timo Oertzen, Pompeu Fabra Barcelona
One of the research goals in constraint satisfaction is to determine the constraint languages whose constraint satisfaction problem (CSP) can be solved by a polynomial time algorithm (we will call...
Determining the consistency of partial tree descriptions (2007)
Bodirsky, Manuel, Kutz, Martin
We present an efficient algorithm that decides the consistency of partial descriptions of ordered trees. The constraint language of these descriptions was introduced by Cornell in computational...
A Direct Decomposition of 3-connected Planar Graphs (2007)
Bodirsky, Manuel, Gröpl, Clemens, Johannsen, Daniel, Kang, Mihyun
We present a decomposition strategy for c-nets, i.\,e., rooted 3-connected planar maps. The decomposition yields an algebraic equation for the number of c-nets with a given number of vertices and a...
Cores of Countably Categorical Structures (2006)
A relational structure is a core, if all its endomorphisms are embeddings. This notion is important for computational complexity classification of constraint satisfaction problems. It is a...
Collapsibility in Infinite-Domain Quantified Constraint Satisfaction. (2006)
Chen, Hubert Ming, Bodirsky, Manuel
In this article, we study the quantified constraint satisfaction problem (QCSP) over infinite domains. We develop a technique called collapsibility that allows one to give strong complexity upper...
On the logical complexity of convex polygon dissections (2006)
Bodirsky, Manuel, Kang, Mihyun, Verbitsky, Oleg
The logical depth of a graph $G$ is the minimum quantifier depth of a first order sentence defining $G$ up to isomorphism in the language of the adjacency and the equality relations. We consider the...
Datalog and Constraint Satisfaction with Infinite templates (2006)
Dalmau, Victor, Bodirsky, Manuel
We relate the expressive power of Datalog and constraint satisfaction with infinite templates. The relationship is twofold: On the one hand, we prove that every non-empty problem that is closed under...
The complexity of equality constraint languages (2006)
Abstract. We apply the algebraic approach to infinite-valued constraint satisfaction to classify the computational complexity of all constraint satisfaction problems with templates that have a highly...
Datalog and constraint satisfaction with infinite templates (2006)
Manuel Bodirsky, Víctor Dalmau
Abstract. On finite structures, there is a well-known connection between the expressive power of Datalog, finite variable logics, the existential pebble game, and bounded hypertree duality. We study...
Datalog and constraint satisfaction with infinite templates (2006)
Manuel Bodirsky, Víctor Dalmau
Abstract. We relate the expressive power of Datalog and constraint satisfaction with infinite templates. The relationship is twofold: On the one hand, we prove that every non-empty problem that is...
The complexity of equality constraint languages (2006)
Abstract. We apply the algebraic approach to infinite-valued constraint satisfaction to classify the computational complexity of all constraint languages where the constraint types are Boolean...
Constraint Satisfaction with Countable Homogeneous Templates (2006)
Bodirsky, Manuel, Nesetril, Jaroslav
For a fixed countable homogeneous relational structure Γ we study the computational problem whether a given finite structure of the same signature homomorphically maps to Γ. This problem is known...
Enumeration and limit laws of series-parallel graphs (2005)
Bodirsky, Manuel, Gimenez, Omer, Kang, Mihyun, Noy, Marc
We show that the number $g_n$ of labelled series-parallel graphs on $n$ vertices is asymptotically $g_n \sim g\cdot n^{-5/2} \gamma^n n!$, where $\gamma$ and $g$ are explicit computable constants. We...
Enumeration of Unlabeled Outerplanar Graphs (2005)
Bodirsky, Manuel, Fusy, Eric, Kang, Mihyun, Vigerske, Stefan
We determine the exact and asymptotic number of unlabeled outerplanar graphs. The exact number g_n of unlabeled outerplanar graphs on n vertices can be computed in polynomial time, and g_n is...
Well-nested drawings as models of syntactic structure (2005)
Manuel Bodirsky, Marco Kuhlmann, Mathias Möhl
Abstract. This paper investigates drawings (totally ordered forests) as models of syntactic structure. It offers a new model-based perspective on lexicalised Tree Adjoining Grammar by characterising...
On the number of series parallel and outerplanar graphs (2005)
Manuel Bodirsky, Omer Giménez, Mihyun Kang, Marc Noy
We show that the number gn of labelled series-parallel graphs on n vertices is asymptotically gn ∼ g · n −5/2 γ n n!, where γ and g are explicit computable constants. We show that the number...
On the number of series parallel and outerplanar graphs (2005)
Manuel Bodirsky, Omer Giménez, Mihyun Kang, Marc Noy
Abstract. We show that the number gn of labelled series-parallel graphs on n vertices is asymptotically gn ∼ g · n −5/2 γ n n!, where γ and g are explicit computable constants. We show that...
Kr'al': Locally Consistent Constraint SatisfactionProblems with Binary Constraints (2005)
An instance of a constraint satisfaction problem is k-consistent if any k constraints of it can be simultaneously satisfied. We focus on constraint languages with a single binary constraint. In this...
Kr'al': Locally Consistent Constraint SatisfactionProblems with Binary Constraints (2005)
Abstract. We study constraint satisfaction problems (CSPs) that are k-consistent in the sense that any k input constraints can be simultaneously satisfied. In this setting, we focus on constraint...
1 Well-Nested Drawings as Models of Syntactic Structure 1 (2005)
Gerhard Jaeger, Paola Monachesi, Gerald Penn, James Rogers, Shuly Wintner, Manuel Bodirsky, ...
and
Beta reduction constraints (2004)
Bodirsky, Manuel, Erk, Katrin, Koller, Alexander, Niehren, Joachim
The constraint language for lambda structures (CLLS) can model lambda terms that are known only partially. In this paper, we introduce beta reduction constraints to describe beta reduction steps...
Underspecified beta reduction (2004)
Bodirsky, Manuel, Erk, Katrin, Koller, Alexander, Niehren, Joachim
For ambiguous sentences, traditional semantics construction produces large numbers of higher-order formulas,which must then be beta-reduced individually. Underspecified versions can produce compact...
Constraint satisfaction with infinite domains (2004)
Constraint Satisfaction Probleme tauchen in vielen Gebieten der theoretischen Informatik auf. Häufig lassen sie sich auf natürliche Weise als Homomorphieprobleme für eine festgelassene Struktur...
Constraint satisfaction with infinite domains (2004)
Constraint Satisfaction Probleme tauchen in vielen Gebieten der theoretischen Informatik auf. Häufig lassen sie sich auf natürliche Weise als Homomorphieprobleme für eine festgelassene Struktur...
A new algorithm for normal dominance constraints (2004)
Bodirsky, Manuel, Duchier, Denys, Miele, Sebastian, Niehren, Joachim
Dominance constraints are logical descriptions of trees. Efficient algorithms for the subclass of normal dominance constraints were recently proposed. We present a new and simpler graph algorithm...
A new algorithm for normal dominance constraints (2004)
Bodirsky, Manuel, Duchier, Denys, Miele, Sebastian, Niehren, Joachim
Dominance constraints are logical descriptions of trees. Efficient algorithms for the subclass of normal dominance constraints were recently proposed. We present a new and simpler graph algorithm...
Constraint satisfaction with infinite domains / (2004)
Berlin, Humboldt-University, Diss., 2004 (Nicht für den Austausch).
Constraint satisfaction with infinite domains [Elektronische Ressource] / (2004)
Berlin, Humboldt-University, Diss., 2004.
A New Algorithm for Normal Dominance Constraints (2004)
Manuel Bodirsky, Denys Duchier, Joachim Niehren, Sebastian Miele
Dominance constraints are logical descriptions of trees. Efficient algorithms for the subclass of normal dominance constraints were recently proposed. We present a new and simpler graph algorithm...
An efficient algorithm for weakly normal dominance constraints (2004)
Manuel Bodirsky, Denys Duchier, Joachim Niehren
Abstract. Dominance constraints are logical descriptions of trees. E-cient algorithms for the subclass of normal dominance constraints were proposed recently. We present a new and simpler graph...
Constraint satisfaction with countable homogeneous templates (2003)
Manuel Bodirsky, Jaroslav Nesetril
Abstract. For a xed countable homogeneous structure we study the computational problem whether a given nite structure of the same relational signature homomorphically maps to. This problem is known...
Generating random outerplanar graphs (2003)
Abstract. We show how to generate labeled and unlabeled outerplanar graphs with n vertices uniformly at random in (expected) polynomial time in n. To generate these graphs, we present a new counting...
Generating Labeled Planar Graphs Uniformly at Random (2003)
Manuel Bodirsky, Clemens Gröpl, Mihyun Kang
We present an expected polynomial time algorithm to generate a labeled planar graph uniformly at random. To generate the planar graphs, we derive recurrence formulas that count all such graphs with n...
Constraint Satisfaction with Countable Homogeneous Templates (2003)
Manuel Bodirsky, Jaroslav Nesetril
For a xed countable homogeneous relational structure we study the computational problem whether a given nite structure of the same signature homomorphically maps to . This problem is known as the...
Generating outerplanar graphs uniformly at random (2003)
supported by the DFG (GRK 588/1) Abstract. We show how to generate labeled and unlabeled outerplanar graphs with n vertices uniformly at random in polynomial time in n. To generate labeled...
Generating labeled planar graphs uniformly at random (2003)
Manuel Bodirsky, Clemens Gröpl, Mihyun Kang
Abstract. We present an expected polynomial time algorithm to generate a labeled planar graph uniformly at random. To generate the planar graphs, we derive recurrence formulas that count all such...
Generating labeled planar graphs uniformly at random (2003)
Manuel Bodirsky, Clemens Gröpl, Mihyun Kang
Abstract. We present a deterministic polynomial time algorithm to sample a labeled planar graph uniformly at random. Our approach uses recursive formulas for the exact number of labeled planar graphs...
Constraint satisfaction with countable homogeneous templates (2003)
Abstract. For a fixed countable homogeneous relational structure Γ we study the computational problem whether a given finite structure of the same signature homomorphically maps to Γ. This problem...
Generating labeled planar graphs uniformly at random (2003)
Manuel Bodirsky, Clemens Gröpl, Mihyun Kang
Abstract. We present an expected polynomial time algorithm to generate a labeled planar graph uniformly at random. To generate the planar graphs, we derive recurrence formulas that count all such...
Pure dominance constraints (2002)
Abstract. We present an efficient algorithm that checks the satisfiability of pure dominance constraints, which is a tree description language contained in several constraint languages studied in...
Beta reduction constraints (2001)
Bodirsky, Manuel, Erk, Katrin, Koller, Alexander, Niehren, Joachim
The constraint language for lambda structures (CLLS) can model lambda terms that are known only partially. In this paper, we introduce beta reduction constraints to describe beta reduction steps...
Underspecified beta reduction (2001)
Bodirsky, Manuel, Erk, Katrin, Koller, Alexander, Niehren, Joachim
For ambiguous sentences, traditional semantics construction produces large numbers of higher-order formulas,which must then be beta-reduced individually. Underspecified versions can produce compact...
Underspecified beta reduction (2001)
Manuel Bodirsky, Alexander Koller, Katrin Erk, Joachim Niehren
www.ps.uni-sb.de/˜{bodirsky|erk|niehren} For ambiguous sentences, traditional semantics construction produces large numbers of higher-order formulas, which must then be β-reduced individually....
Beta reduction constraints (2001)
Manuel Bodirsky, Er Koller, Joachim Niehren
Abstract. The constraint language for lambda structures (CLLS) can model lambda terms that are known only partially. In this paper, we introduce beta reduction constraints to describe beta reduction...
Underspecified beta reduction (2001)
Manuel Bodirsky, Alexander Koller, Katrin Erk, Joachim Niehren
For ambiguous sentences, traditional semantics construction produces large numbers of higher-order formulas, which must then be -reduced individually. Underspecified versions can produce compact...
Beta reduction constraints (2001)
www.ps.uni-sb.de/~{bodirsky,erk,koller,niehren} Abstract. The constraint language for lambda structures (CLLS) can model lambda terms that are known only partially. In this paper, we introduce beta...