I maj 2004 genomfördes en enkätundersökning som riktades till alla doktorander vid Linköpings universitet. De frågeområden som enkäten behandlade inkluderade doktorandens bakgrund och nuvarande status; handledningssituationen samt forsknings- och arbetsmiljö; upplevd särbehandling; forskarutbildningskurser och seminarier; pedagogisk utveckling och undervisning, samt ett antal frågor om hur doktoranden såg på sin forskarutbildning, sin egen insats och på framtiden. Dessutom fanns möjlighet att i fritext ange vad som var positivt respektive negativt med utbildningen, samt att ge förslag på vad som borde förändras och bevaras.

Enkäten sändes till de cirka 1 360 personer vars e-postadresser var tillgängliga. Närmare 70 %, eller över 900 personer, svarade på enkäten; i ungefär samma omfattning på samtliga fakulteter. Ungefär 5 % uppgav inte någon fakultetstillhörighet. Cirka 45 % av de svarande angav att de var kvinnor, medan 52 % angav att de var män. Det var dock stora variationer i könsfördelningen på fakultetsnivå. Kvinnornas medianålder var något högre än männens, och åldersspridningen var störst på Hälsouniversitetet (HU). Doktoranderna vid Linköpings tekniska högskola (LiTH) var i genomsnitt yngst och en mindre andel av dem, jämfört med övriga, hade hemmavarande barn. Det var en högre andel kvinnor än män som hade hemmavarande barn. Ungefär tre av fyra bodde i Norrköping eller Linköping; en högre andel på LiTH, och en lägre andel på Filosofisk fakultet (Fil fak) och Utbildningsvetenskap (UV).

Drygt hälften av alla som svarade på frågan hade genomfört hälften eller mindre av sin forskarutbildning. Att vara antagen till licentiatexamen var betydligt vanligare på LiTH (ca 12 %) än på övriga fakulteter. Drygt en fjärdedel av de svarande deltog i någon forskarskola. Det vanligast skälet till att ha gjort ett längre uppehåll var föräldraledighet (8 %) följt av förvärvsarbete (5 %).

Den vanligaste formen av försörjning var doktorandanställning, men det fanns stora skillnader mellan fakulteterna/motsvarande. HU hade lägst andel. En tredjedel av doktoranderna där hade istället klinisk tjänst. Drygt 80 % av de forskarstuderande vid LiTH hade doktorandanställning. Att enbart ha utbildningsbidrag var sällsynt på samtliga fakulteter, medan kombinationen utbildningsbidrag och assistenttjänst förekom; och då mest frekvent vid HU (drygt 12 %). Den vanligaste uppgivna aktivitetsgraden oavsett fakultet var mellan 90 och 100 % (cirka 25 % av de svarande) medan det på HU fanns en andel – nära 20 % – med mycket låg aktivitetsgrad (0–10 %).

Doktoranderna var tämligen nöjda med sin utbildning. På en femgradig skala där 5 stod för ”mycket bra” och 1 ”mycket dålig” hamnade medelbetyget på forskarutbildningen på 3,65. Doktoranderna på Filosofisk fakultet och LiTH satte ett något högre betyg, men variationerna mellan fakulteterna var små. Betyget på den egna insatsen sattes av de allra flesta något lägre, medelvärdet var 3,60 på samma skala. De mer detaljerade frågorna om handledning och avhandlingsarbete hade i flera fall högre medelvärde: Handledarens intresse för doktorandens forskning, handledarens läsning av texter, förekomsten av konstruktiv kritik och doktorandens förtroende för handledaren låg nära värdet 4 på den femgradiga skalan. Lägre medelvärden gavs på frågan om handledaren underlättar för doktoranden att få kontakt med andra forskare. Tiden som användes för handledning skiftade en del mellan fakulteterna, men sammanfattningsvis fick cirka 80 % av alla doktorander 1–10 timmar handledning per månad. Filosofisk fakultet och Utbildningsvetenskap hamnade oftare i den nedre delen av intervallet och LiTH samt HU i den högre delen. Uppfattningen att tiden som gavs svarade mot behovet skiftade. Mest nöjda med tidens omfattning var doktoranderna på Utbildningsvetenskap; minst nöjd var man på LiTH.

På frågorna om forskarutbildningskurser hamnade medelvärdena lägre än på frågorna om handledning. Det var liten skillnad mellan forskarskoledoktorander och övriga på dessa frågor.

Rent allmänt var alla mycket nöjda med sin forsknings- och arbetsmiljö. Genomgående fick frågorna inom det området högt medelbetyg, med undantag för dem som rörde tillgången till nationella och framför allt internationella forskarnätverk. Den sociala miljön i doktorandgruppen skattades högre än densamma på institutionen i sin helhet.

Enkäten innehöll även frågor om upplevd positiv och negativ särbehandling. Cirka 50 personer, med få undantag kvinnor, instämde i att de upplevt negativ särbehandling på grund av kön (svarade 4 eller 5 på den femgradiga skalan). Ingen fakultet utmärkte sig i detta avseende.

Institutioner med en jämn könsfördelning föreföll ha färre fall av upplevd negativ särbehandling. De som upplevt negativ särbehandling på grund av etnisk bakgrund, sexuell läggning eller social bakgrund var färre till antalet. Även positiv särbehandling hade upplevts – antalet svar var av samma storleksordning som för negativ särbehandling. Spridningen över fakulteter och institutioner var även här stor.

Efter disputationen kunde ungefär 70 % tänka sig en postdoc-period utomlands. Huvudskälet till att inte vilja åka var vanligen hänsyn till familjen, det vill säga situationen för barn och partner. Omkring hälften såg sina möjligheter som goda eller mycket goda att få ett arbete direkt efter examen.

The connection between constraints and universal algebra has been looked at in, e.g Jeavons, Cohen and Pearson, 1998, and has given interesting results. Since the connection between universal algebra and category theory is so obvious, we will in this paper investigate if the usage of category theory has any impact on the results and/or reasoning and if anything can be gained from this approach. We construct categories of problem instances and of solutions to these, and, via an adjunction between these categories, note that the algebras give us a way of describing 'minimality of a problem,' while the coalgebras give a criterion for deciding if a given set of solutions can be expressed by a constraint problem of a given arity. Another pair of categories, of sets of relations and of sets of operations on a fixed set, is defined, and this time the algebras we get give an indication of the 'expressive power' of a set of constraint types, while the coalgebras tell us about the computational complexity of the corresponding constraint problem.

The connection between constraints and universal algebra has been looked at in, e.g., Jeavons, Cohen and Pearson, 1998, and has given interesting results. Since the connection between universal algebra and category theory is so obvious, we will in this paper investigate if the usage of category theory has any impact on the results and/or reasoning and if anything can be gained from this approach. We construct categories of problem instances and of solutions to these, and, via an adjunction between these categories, note that the algebras give us a way of describing 'minimality of a problem,' while the coalgebras give a criterion for deciding if a given set of solutions can be expressed by a constraint problem of a given arity. Another pair of categories, of sets of relations and of sets of operations on a fixed set, is defined, and this time the algebras we get give an indication of the 'expressive power' of a set of constraint types, while the coalgebras tell us about the computational complexity of the corresponding constraint problem. © 2000 Published by Elsevier Science B.V.

In this thesis, we will discuss the construction of algorithms for solving Constraint Satisfaction Problems (CSPs), and describe two new ways of approaching them. Both approaches are based on the idea that it is sometimes faster to solve a large number of restricted problems than a single, large, problem. One of the strong points of these methods is that the intuition behind them is fairly simple, which is a definite advantage over many techniques currently in use.

The first method, the covering method, can be described as follows: We want to solve a CSP with n variables, each having a domain with d elements. We have access to an algorithm which solves problems where the domain has size e < d, and we want to cover the original problem using a number of restricted instances, in such a way that the solution set is preserved. There are two ways of doing this, depending on the amount of work we are willing to invest; either we construct an explicit covering and end up with a deterministic algorithm for the problem, or we use a probabilistic reasoning and end up with a probabilistic algorithm.

The second method, called the partitioning method, relaxes the demand on the underlying algorithm. Instead of having a single algorithm for solving problems with domain less than d, we allow an arbitrary number of them, each solving the problem for a different domain size. Thus by splitting, or partitioning, the domain of the large problem, we again solve a large number of smaller problems before arriving at a solution.

Armed with these new techniques, we study a number of different problems; the decision problems (d, l)-CSP and k-Colourability, together with their counting counterparts, as well as the optimisation problems Max Ind CSP, Max Value CSP, Max CSP, and Max Hamming CSP. Among the results, we find a very fast, polynomial space algorithm for determining k-colourability of graphs.

We present a quantum algorithm for finite domain constraint solving, where the constraints have arity 2. It is complete and runs in time, where d is size of the domain of the variables and n the number of variables. For the case of d=3 we provide a method to obtain an upper time bound of . Also for d=5 the upper bound has been improved. Using this method in a slightly different way we can decide 3-colourability in O(1.2185^n) time.

Counting the number of solutions to CSP instances has vast applications in several areas ranging from statistical physics to artificial intelligence. We provide a new algorithm for counting the number of solutions to binary CSP s which has a time complexity ranging from O ((d/4 . alpha(4))(n)) to O((alpha + alpha(5) + [d/4 - 1] . alpha(4))(n)) (where alpha approximate to 1.2561) depending on the domain size d greater than or equal to 3. This is substantially faster than previous algorithms, especially for small d. We also provide an algorithm for counting k-colourings in graphs and its running time ranges from O ([log(2) k](n)) to O ([log(2) k + 1](n)) depending on k greater than or equal to 4. Previously, only an O(1.8171(n)) time algorithm for counting 3-colourings were known, and we improve this upper bound to O(1.7879(n)).

Counting the number of solutions to CSP instances has applications in several areas, ranging from statistical physics to artificial intelligence. We give an algorithm for counting the number of solutions to binary CSPs, which works by transforming the problem into a number of 2-SAT instances, where the total number of solutions to these instances is the same as those of the original problem. The algorithm consists of two main cases, depending on whether the domain size d is even, in which case the algorithm runs in O(1.3247^n*(d/2)^n) time, or odd, in which case it runs in O(1.3247^n*((d^2+d+2)/4)^(n/2)) if d=4*k+1, and O(1.3247^n*((d^2+d)/4)^(n/2)) if d=4*k+3. We also give an algorithm for counting the number of possible 3-colourings of a given graph, which runs in O(1.8171^n), an improvement over our general algorithm gained by using problem specific knowledge. 

We study two constraint satisfaction optimisation problems: The Max Value problem for CSPs, which, somewhat simplified, aims at maximising the sum of the (weighted) variable values in the solution, and the Max Ind problem, where the goal is to find a satisfiable subinstance of the original instance containing as many variables as possible. Both problems are NP-hard to approximate within n^(1-e), e>0, where n is the number of variables in the problems, which implies that it is of interest to find exact algorithms. By exploiting properties of the microstructure, we construct algorithms for solving instances of these problems with small domain sizes, and then, using a probabilistic reasoning, we show how to get algorithms for more general versions of the problems. The resulting algorithms have running times of O((0.585d)^n) for Max Value (d,2)-CSP, and O((0.503d)^n) for MaxInd (d,2)-CSP. Both algorithms represent the best known theoretical bounds for their respective problem, and, more importantly, the methods used are applicable to a wide range of optimisation problems. 

This book constitutes the thoroughly refereed and extended post-proceedings of the Joint ERCIM/CoLogNet International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2005, held in Uppsala, Sweden in June 2005.

Besides papers taken from the workshop, others are submitted in response to an open call for papers after the workshop.

The 12 revised full papers presented were carefully reviewed and selected for inclusion in the book. The papers are organized in topical sections on global constraints, search and heuristics, language and implementation issues, and modeling.

This book constitutes the thoroughly refereed and extended post-proceedings of the Joint ERCIM/CoLogNet International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2005, held in Uppsala, Sweden in June 2005.

Besides papers taken from the workshop, others are submitted in response to an open call for papers after the workshop.

The 12 revised full papers presented were carefully reviewed and selected for inclusion in the book. The papers are organized in topical sections on global constraints, search and heuristics, language and implementation issues, and modeling.

The paper presents a framework for hybrid combination of rule languages with constraint languages including but not restricted to Description-Logic-based ontology languages. It shows how reasoning in a combined language can be done by interfacing reasoners of the component languages. A prototype system based on the presented principle integrates Datalog with OWL by interfacing XSB Prolog [2] with a DIG-compliant [1] DL reasoner (e.g. Racer [17]).

We present typing rules for the Web query language Xcerpt.

The rules provide a descriptive type system: the typing of a program is an

approximation of its semantics. The rules can also be seen as an abstract

form of a type inference algorithm (presented in previous work), and as a

stage in a formal soundness proof of the algorithm. The paper considers

a substantial fragment of Xcerpt; the main restriction is that we deal

with data terms corresponding to trees (instead of general graphs), and

we do not deal with Xcerpt rule chaining. We provide a formal semantics

for the fragment of Xcerpt and a soundness theorem for the presented

type system.

The class of constraint satisfaction problems (CSPs) over finite domains has been shown to be NP-complete, but many tractable subclasses have been identified in the literature. In this paper we are interested in restrictions on the types of constraint relations in CSP instances. By a result of Jeavons et al. we know that a key to the complexity of classes arising from such restrictions is the closure properties of the sets of relations. It has been shown that sets of relations that are closed under constant, majority, affine, or associative, commutative, and idempotent (ACI) functions yield tractable subclasses of CSP. However, it has been unknown whether other closure properties may generate tractable subclasses. In this paper we introduce a class of tractable (in fact, SL-complete) CSPs based on bipartite graphs. We show that there are members of this class that are not closed under constant, majority, affine, or ACI functions, and that it, therefore, is incomparable with previously identified classes.

We study logical techniques for deciding the computational complexity of infinite-domain constraint satisfaction problems (CSPs). For the fundamental algebraic structure where are the real numbers and L ₁,L ₂,... is an enumeration of all linear relations with rational coefficients, we prove that a semilinear relation R (i.e., a relation that is first-order definable with linear inequalities) either has a quantifier-free Horn definition in Γ or the CSP for is NP-hard. The result implies a complexity dichotomy for all constraint languages that are first-order expansions of Γ: the corresponding CSPs are either in P or are NP-complete depending on the choice of allowed relations. We apply this result to two concrete examples (generalised linear programming and metric temporal reasoning) and obtain full complexity dichotomies in both cases.

We present an efficient algorithm to find an optimal integer solution of a given system of 2-variable equalities and I-variable inequalities with respect to a given linear objective function. Our algorithm has worst-case running time in O(N-2) where N is the number of bits in the input.

Reasoning about temporal and spatial information is a common task in computer science, especially in the field of artificial intelligence. The topic of this thesis is the study of such reasoning from a computational perspective. We study a number of different qualitative point based formalisms for temporal reasoning and provide a complete classification of computational tractability for different time models. We also develop more general methods which can be used for proving tractability and intractability of other relational algebras. Even though most of the thesis pertains to qualitative reasoning the methods employed here can also be used for quantitative reasoning. For instance, we introduce a tractable and useful extension to the quantitative point based formalism STP. This extension gives the algebra an expressibility which subsumes the largest tractable fragment of the augmented interval algebra and has a faster and simpler algorithm for deciding consistency.

The use of disjunctions in temporal formalisms is of great interest not only since disjunctions are a key element in different logics but also since the expressibility can be greatly enhanced in this way. If we allow arbitrary disjunctions, the problems under consideration typically become intractable and methods to identify tractable fragments of disjunctive formalisms are therefore useful. One such method is to use the independence property. We present an automatic method for deciding this property for many relational algebras. Furthermore, we show how this concept can not only be used for deciding tractability of sets of relations but also to demonstrate intractability of relations not having this property. Together with other methods for making total classifications of tractability this goes a long way towards easing the task of classifying and understanding relational algebras.

The tractable fragments of relational algebras are sometimes not expressive enough to model real-world problems and a backtracking solver is needed. For these cases we identify another property among relations which can be used to aid general backtracking based solvers to finnd solutions faster.

We investigate the computational complexity of temporal reasoning in different time models such as totally-ordered, partially-ordered and branching time. Our main result concerns the satisfiability problem for point algebras and point algebras extended with disjunctions—for these problems, we identify all tractable subclasses. We also provide a number of additional results; for instance, we present a new time model suitable for reasoning about systems with a bounded number of unsynchronized clocks, we investigate connections with spatial reasoning and we present improved algorithms for deciding satisfiability of the tractable point algebras.

Efficient reasoning about temporal constraints over nonlinear time models is vital in numerous application areas, such as planning, distributed systems and cooperating agents. We identify all tractable subclasses of the point algebra for partially-ordered time and examine one large, nontrivial tractable subclass of the point algebra for branching time.

An important question in constraint satisfaction is how to restrict the problem to ensure tractability (since the general problem is NP-hard). The use of disjunctions has proven to be a useful method for constructing tractable constraint classes from existing classes; the well-known ‘max-closed’ and ‘ORD-Horn’ constraints are examples of tractable classes that can be constructed this way. Three sufficient conditions (the guaranteed satisfaction property, 1-independence and 2-independence) that each ensure the tractability of constraints combined by disjunctions have been proposed in the literature. We show that these conditions are both necessary and sufficient for tractability in three different natural classes of disjunctive constraints. This suggests that deciding this kind of property is a very important task when dealing with disjunctive constraints. We provide a simple, automatic method for checking the 1-independence property—this method is applicable whenever the consistency of the constraints under consideration can be decided by path-consistency. Our method builds on a connection between independence and refinements (which is a way of reducing one constraint satisfaction problem to another.)

This book constitutes the refereed proceedings of the International Workshop on Principles and Practice of Semantic Web Reasoning, PPSWR 2003, held in Mumbai, India in December 2003 as satellite meeting of ICLP 2003. The 13 revised full papers presented were carefully reviewed and selected for inclusion in the proceedings. The papers are organized in topical sections on foundations of semantic Web reasoning, reasoning in practice, query- and rule-languages, and semantics and knowledge representation.

This paper discusses subtyping of tree-structured data encountered on the Web, e.g. XML and HTML data. Our long range objective is to define a type system for Web and/or Semantic Web query languages amenable to static type checking. We propose a type formalism motivated by XML Schema and accommodating two concepts of subtyping: inclusion subtyping (corresponding to XML Schema notion of type restriction) and extension subtyping (motivated by XML Schema's type extension). We present algorithms for checking both kinds of subtyping. The algorithms are polynomial if certain conditions are imposed on the type definitions, the conditions seem natural and not too restrictive.

Complexity analysis of planning is problematic. Even very simple planning languages are PSPACE-complete, yet cannot model many simple problems naturally. Many languages with much more powerful features are also PSPACE-complete. It is thus difficult to separate planning languages in a useful way and to get complexity figures that better reflect reality.This paper introduces new methods for complexity analysis of planning and similar combinatorial search problems, in order to achieve more precision and complexity separations than standard methods allow. Padding instances with the solution size yields a complexity measure that is immune to this factor and reveals other causes of hardness, that are otherwise hidden. Further combining this method with limited nondeterminism improves the precision, making even finer separations possible. We demonstrate with examples how these methods can narrow the gap between theory and practice.

Most planning formalisms allow instances with shortest plans of exponential length. While such instances are problematic, they are usually unavoidable and can occur in practice. There are several known cases of restricted planning problems where plans can be exponential but always have a compact (ie. polynomial) representation, often using recursive macros. Such compact representations are important since exponential plans are difficult both to use and to understand. We show that these results do not extend to the general case, by proving a number of bounds for compact representations of plans under various criteria, like efficient sequential or random access of actions. Further, we show that it is unlikely to get around this by reformulating planning into some other problem. The results are discussed in the context of abstraction, macros and plan explanation.

This paper formally presents a class of planning problems, the SAS-PUS class, which allows non-binary state variables and parallel execution of actions. The class is proven to be tractable, and we provide a sound and complete, polynomial time algorithm for planning within this class. Since the SAS-PUS class is an extension of the previously presented SAS-PUBS class, this result means that we are getting closer to tackling realistic planning problems in sequential control. In such problems, a restricted problem representation is often sufficient but the size of the problems make tractability an important issue.

This article describes a polynomial-time, O(n³), planning algorithm for a limited class of planning problems. Compared to previous work on complexity of algorithms for knowledge-based or logic-based planning, our algorithm achieves computational tractability, but at the expense of only applying to a significantly more limited class of problems. Our algorithm is proven correct, and it always returns a parallel minimal plan if there is a plan at all.

Many combinatorial search problems can be expressed as 'constraint satisfaction problems'. This class of problems is known to be NP-hard in general, but a number of restricted constraint classes have been identified which ensure tractability. This paper presents the first general results on combining tractable constraint classes to obtain larger, more general, tractable classes. We give examples to show that many known examples of tractable constraint classes, from a wide variety of different contexts, can be constructed from simpler tractable classes using a general method. We also construct several new tractable classes that have not previously been identified.

We here study MAX HAMMING XSAT, i.e., the problem of finding two XSAT models at maximum Hamming distance. By using a recent XSAT solver as an auxiliary function, an O(2(n)) time algorithm can be constructed, where n is the number of variables. This upper time bound can be further improved to O(1.8348(n)) by introducing a new kind of branching, more directly suited for finding models at maximum Hamming distance. The techniques presented here are likely to be of practical use as well as of theoretical value, proving that there are non-trivial algorithms for maximum Hamming distance problems.

This book constitutes the refereed proceedings of the 11th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR 2004, held in Montevideo, Uruguay in March 2005.  The 33 revised full papers presented together with abstracts of 4 invited papers were carefully reviewed and selected from 77 submissions. The papers address all current issues in logic programming, automated reasoning, and AI logics in particular description logics, fuzzy logic, linear logic, multi-modal logic, proof theory, formal verification, protocol verification, constraint logic programming, programming calculi, theorem proving, etc

This thesis presents exact means to solve a family of NP-hard problems. Starting with the well-studied Exact Satisfiability problem (XSAT) parents, siblings and daughters are derived and studied, each with interesting practical and theoretical properties. While developing exact algorithms to solve the problems, we gain new insights into their structure and mutual similarities and differences.

Given a Boolean formula in CNF, the XSAT problem asks for an assignment to the variables such that each clause contains exactly one true literal. For this problem we present an O(1.1730ⁿ) time algorithm, where n is the number of variables. XSAT is a special case of the General Exact Satisfiability problem which asks for an assignment such that in each clause exactly i literals be true. For this problem we present an algorithm which runs in O(2^(1-ε⁾ n) time, with 0 < ε < 1 for every fixed i; for i=2, 3 and 4 we have running times in O(1.4511ⁿ), O(1.6214ⁿ) and O(1.6848ⁿ) respectively.

For the counting problems we present an O(1.2190ⁿ) time algorithm which counts the number of models for an XSAT instance. We also present algorithms for #2SATw and #3SATw, two well studied Boolean problems. The algorithms have running times in O(1.2561ⁿ) and O(1.6737ⁿ) respectively.

Finally we study optimisation problems: As a variant of the Maximum Exact Satisfiability problem, consider the problem of finding an assignment exactly satisfying a maximum number of clauses while the rest are left with no true literal. This problem is reducible to #2SATw without the addition of new variables and thus is solvable in time O(1.2561ⁿ). Another interesting optimisation problem is to find two XSAT models which differ in as many variables as possible. This problem is shown to be solvable in O(1.8348ⁿ) time.

We present four polynomial space and exponential time algorithms for variants of the EXACT SATISFIABILITY problem. First, an O(1.1120n) (where n is the number of variables) time algorithm for the NP-complete decision problem of EXACT 3-SATISFIABILITY, and then an O(1.1907n) time algorithm for the general decision problem of EXACT SATISFIABILITY. The best previous algorithms run in O(1.1193n) and O(1.2299n) time, respectively. For the #P-complete problem of counting the number of models for EXACT 3-SATISFIABILITY we present an O(1.1487n) time algorithm. We also present an O(1.2190n) time algorithm for the general problem of counting the number of models for EXACT SATISFIABILITY, presenting a simple reduction, we show how this algorithm can be used for computing the permanent of a 0/1 matrix. © 2004 Elsevier B.V. All rights reserved.

We present an O(1.3247ⁿ) algorithm for counting the number of satisfying assignments for instances of 2-SAT and an O(1.6894ⁿ) algorithm for instances of 3-SAT. This is an improvement compared to the previously best known algorithms running in O(1.381ⁿ) and O(1.739ⁿ) time, respectively.

We here present algorithms for counting models and max-weight models for 2SAT and 3SAT formulae. They use polynomial space and run in O(1.2561ⁿ) and O(1.6737ⁿ) time, respectively, where n is the number of variables. This is faster than the previously best algorithms for counting non-weighted models for 2SAT and 3SAT, which run in O(1.3247ⁿ) and O(1.6894ⁿ) time, respectively. In order to prove these time bounds, we develop new measures of formula complexity, allowing us to conveniently analyze the effects of certain factors with a large impact on the total running time. We also provide an algorithm for the restricted case of separable 2SAT formulae, with fast running times for well-studied input classes. For all three algorithms we present interesting applications, such as computing the permanent of sparse 0/1 matrices.

We present a logic programming based asynchronous multi-agent system in which agents can communicate with one another; update themselves and each other; abduce hypotheses to explain observations, and use them to generate actions. The knowledge base of the agents is comprised of generalized logic programs, integrity constraints, active rules, and of abducibles. We characterize the interaction among agents via an asynchronous transition rule system, and provide a stable models based semantics. An example is developed to illustrate how our approach works.

We present a logic programming based asynchronous multi-agent system in which agents can communicate with one another, update themselves and each other, abduce hypotheses to explain observations, and use them to generate actions. The knowledge base of the agents is comprised of generalized logic programs, integrity constraints, active rules, and of abducibles. We characterize the interaction among agents via an asynchronous transition rule system, and provide a stable models based semantics. An example is developed to illustrate how our approach works. © 2002 Published by Elsevier Science B.V.