Skip to main content

Research Repository

Advanced Search

Outputs (5)

The complexity of achievement and maintenance problems in agent-based systems (2003)
Journal Article
Stewart, I. (2003). The complexity of achievement and maintenance problems in agent-based systems. Artificial Intelligence, 146(2), 175-191. https://doi.org/10.1016/s0004-3702%2803%2900014-6

We completely classify the computational complexity of the basic achievement and maintenance agent design problems in bounded environments when these problems are parameterized by the number of environment states and the number of agent actions. The... Read More about The complexity of achievement and maintenance problems in agent-based systems.

Some problems not definable using structure homomorphisms (2003)
Journal Article
Madelaine, F., & Stewart, I. (2003). Some problems not definable using structure homomorphisms. Ars combinatoria, 67, 153-159

We exhibit some problems definable in Feder and Vardi's logic MMSNP that are not in the class CSP of constraint satisfaction problems. Whilst some of these problems have previously been shown to be in MMSNP (that is, definable in MMSNP) but not in CS... Read More about Some problems not definable using structure homomorphisms.

Using program schemes to capture polynomial-time logically on certain classes of structures (2003)
Journal Article
Stewart, I. (2003). Using program schemes to capture polynomial-time logically on certain classes of structures. LMS journal of computation and mathematics, 6, 40-67

We continue the study of the expressive power of certain classes of program schemes on finite structures, in relation to more mainstream logics studied in finite model theory and to computational complexity. We show that there exists a program scheme... Read More about Using program schemes to capture polynomial-time logically on certain classes of structures.

Greedy algorithms, H-colourings and a complexity-theoretic dichotomy (2003)
Journal Article
Puricella, A., & Stewart, I. (2003). Greedy algorithms, H-colourings and a complexity-theoretic dichotomy. Theoretical Computer Science, 290(3), 1897-1913. https://doi.org/10.1016/s0304-3975%2802%2900329-8

Let H be a fixed undirected graph. An H-colouring of an undirected graph G is a homomorphism from G to H. If the vertices of G are partially ordered then there is a generic non-deterministic greedy algorithm which computes all lexicographically first... Read More about Greedy algorithms, H-colourings and a complexity-theoretic dichotomy.

A note on first-order projections and games (2003)
Journal Article
Arratia, A., & Stewart, I. (2003). A note on first-order projections and games. Theoretical Computer Science, 290(3), 2085-2093. https://doi.org/10.1016/s0304-3975%2802%2900491-7

We show how the fact that there is a first-order projection from the problem TC (transitive closure) to some other problem $\Omega$ enables us to automatically deduce that a natural game problem, $\mathcal{LG}(\Omega)$, whose instances are labelled i... Read More about A note on first-order projections and games.