Outputs (3158)

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.

Matching games : the least core and the nucleolus (2003)
Journal Article
Kern, W., & Paulusma, D. (2003). Matching games : the least core and the nucleolus. Mathematics of Operations Research, 28(2), 294-308. https://doi.org/10.1287/moor.28.2.294.14477

A matching game is a cooperative game defined by a graph G = (V, E). The player set is V and the value of a coalition S # V is defined as the size of a maximum matching in the subgraph induced by S. We show that the nucleolus of such games can be com... Read More about Matching games : the least core and the nucleolus.

Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey (2003)
Presentation / Conference Contribution
Krokhin, A., Bulatov, A., & Jeavons, P. (2003, May). Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey. Presented at 33rd International Symposium on Multiple-Valued Logic (ISMVL'03)

Many computational problems arising in artificial intelligence, computer science and elsewhere can be represented as constraint satisfaction and optimization problems. In this short survey we discuss an approach that is related to the algebraic compo... Read More about Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey.

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.

Finding Paths in Graphs Avoiding Forbidden Transitions; (2003)
Journal Article
Szeider, S. (2003). Finding Paths in Graphs Avoiding Forbidden Transitions;. Discrete Applied Mathematics, 126(2-3), 261-273. https://doi.org/10.1016/s0166-218x%2802%2900251-2

Let v be a vertex of a graph G; a transition graph T(v) of v is a graph whose vertices are the edges incident with v. We consider graphs G with prescribed transition systems T={T(v) | vV(G)}. A path P in G is called T-compatible, if each pair uv,vw o... Read More about Finding Paths in Graphs Avoiding Forbidden Transitions;.

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.

The natural work-stealing algorithm is stable (2003)
Journal Article
Berenbrink, P., Friedetzky, T., & Goldberg, L. (2003). The natural work-stealing algorithm is stable. SIAM Journal on Computing, 32(5), 1260-1279. https://doi.org/10.1137/s0097539701399551

In this paper we analyze a very simple dynamic work-stealing algorithm. In the work-generation model, there are n (work) generators. A generator-allocation function is simply a function from the n generators to the n processors. We consider a fixed,... Read More about The natural work-stealing algorithm is stable.

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.

Solving order constraints in logarithmic space (2003)
Presentation / Conference Contribution
Krokhin, A., & Larose, B. (2003, January). Solving order constraints in logarithmic space. Presented at Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science {(STACS'03) Berlin, Berlin

We combine methods of order theory, finite model theory, and universal algebra to study, within the constraint satisfaction framework, the complexity of some well-known combinatorial problems connected with a finite poset. We identify some conditions... Read More about Solving order constraints in logarithmic space.

Identifying Cause and Effect Relations between Events in Concurrent Event-Based Components (2003)
Presentation / Conference Contribution
Dias, M., & Richardson, D. J. (2002, September). Identifying Cause and Effect Relations between Events in Concurrent Event-Based Components. Presented at 17th IEE International Conference on Automated Software Engineering, Edinburgh, UK

Concurrent event-based components present characteristics that impose difficulties in understanding their dynamic behavior, mainly for interpreting the cause and effect relations between input and output events in component interactions. In this pape... Read More about Identifying Cause and Effect Relations between Events in Concurrent Event-Based Components.