Skip to main content

Research Repository

Advanced Search

All Outputs (24)

Simulating Errors in Web Services. (2004)
Journal Article
Looker, N., Munro, M., & Xu, J. (2004). Simulating Errors in Web Services. International journal of simulation: systems, science & technology, 5(5), 29-37

Complexity classification in qualitative temporal constraint reasoning (2004)
Journal Article
Jonsson, P., & Krokhin, A. (2004). Complexity classification in qualitative temporal constraint reasoning. Artificial Intelligence, 160(1-2), 35-51. https://doi.org/10.1016/j.artint.2004.05.010

We study the computational complexity of the qualitative algebra which is a temporal constraint formalism that combines the point algebra, the point-interval algebra and Allen's interval algebra. We identify all tractable fragments and show that ever... Read More about Complexity classification in qualitative temporal constraint reasoning.

Recognizing frozen variables in constraint satisfaction problems (2004)
Journal Article
Jonsson, P., & Krokhin, A. (2004). Recognizing frozen variables in constraint satisfaction problems. Theoretical Computer Science, 329(1-3), 93-113. https://doi.org/10.1016/j.tcs.2004.08.006

In constraint satisfaction problems over finite domains, some variables can be frozen, that is, they take the same value in all possible solutions. We study the complexity of the problem of recognizing frozen variables with restricted sets of constra... Read More about Recognizing frozen variables in constraint satisfaction problems.

The computational complexity of the elimination problem in generalized sports competitions (2004)
Journal Article
Kern, W., & Paulusma, D. (2004). The computational complexity of the elimination problem in generalized sports competitions. Discrete Optimization, 1(2), 205-214. https://doi.org/10.1016/j.disopt.2003.12.003

Consider a sports competition among various teams playing against each other in pairs (matches) according to a previously determined schedule. At some stage of the competition one may ask whether a particular team still has a (theoretical) chance to... Read More about The computational complexity of the elimination problem in generalized sports competitions.

On the support of recursive subdivision (2004)
Journal Article
Ivrissimtzis, I., Sabin, M., & Dodgson, N. (2004). On the support of recursive subdivision. ACM Transactions on Graphics, 23(4), 1043-1060. https://doi.org/10.1145/1027411.1027417

We study the support of subdivision schemes: that is, the region of the subdivision surface, which is affected by the displacement of a single control point. Our main results cover the regular case, where the mesh induces a regular Euclidean tessella... Read More about On the support of recursive subdivision.

Proving BDI properties of agent-oriented programming languages : the asymmetry thesis principles in AgentSpeak(L) (2004)
Journal Article
Bordini, R. H., & Moreira, A. F. (2004). Proving BDI properties of agent-oriented programming languages : the asymmetry thesis principles in AgentSpeak(L). Annals of Mathematics and Artificial Intelligence, 42(1-3), 197-226. https://doi.org/10.1023/b%3Aamai.0000034527.45635.e5

In this paper, we consider each of the nine BDI principles defined by Rao and Georgeff based on Bratman's asymmetry thesis, and we verify which ones are satisfied by Rao's AgentSpeak(L), a logic programming language inspired by the BDI architecture f... Read More about Proving BDI properties of agent-oriented programming languages : the asymmetry thesis principles in AgentSpeak(L).

Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable (2004)
Journal Article
Szeider, S. (2004). Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable. Journal of Computer and System Sciences, 69(4), 656-674. https://doi.org/10.1016/j.jcss.2004.04.009

Recognition of minimal unsatisfiable CNF formulas (unsatisfiable CNF formulas which become satisfiable if any clause is removed) is a classical DP-complete problem. It was shown recently that minimal unsatisfiable formulas with n variables and n+k cl... Read More about Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable.

Counting Consistent Phylogenetic Trees is #P-complete (2004)
Journal Article
Bordewich, M., Semple, C., & Talbot, J. (2004). Counting Consistent Phylogenetic Trees is #P-complete. Advances in Mathematics, 33(2), 416-430. https://doi.org/10.1016/j.aam.2003.08.006

Reconstructing phylogenetic trees is a fundamental task in evolutionary biology. Various algorithms exist for this purpose, many of which come under the heading of `supertree methods'. These methods amalgamate a collection Ρ of phylogenetic trees int... Read More about Counting Consistent Phylogenetic Trees is #P-complete.

Amalgamations of factorizations of complete equipartite graphs, (2004)
Journal Article
Hilton, A., & Johnson, M. (2004). Amalgamations of factorizations of complete equipartite graphs,. Discrete Mathematics, 284(1-3), 157-175. https://doi.org/10.1016/j.disc.2003.11.030

Let t be a positive integer, and let L=(l1,…,lt) and K=(k1,…,kt) be collections of nonnegative integers. A graph has a (t,K,L) factorization if it can be represented as the edge-disjoint union of factors F1,…,Ft where, for 1it, Fi is ki-regular and a... Read More about Amalgamations of factorizations of complete equipartite graphs,.

A maximal tractable class of soft constraints (2004)
Journal Article
Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2004). A maximal tractable class of soft constraints. Journal of Artificial Intelligence Research, 22, 1-22. https://doi.org/10.1613/jair.1400

Many researchers in artificial intelligence are beginning to explore the use of soft constraints to express a set of (possibly conflicting) problem requirements. A soft constraint is a function defined on a collection of variables which associates so... Read More about A maximal tractable class of soft constraints.

Evolutions of Polygons in the Study of Subdivision Surfaces (2004)
Journal Article
Ivrissimtzis, I., & Seidel, H. (2004). Evolutions of Polygons in the Study of Subdivision Surfaces. Computing, 72(1-2), 93-103. https://doi.org/10.1007/s00607-003-0049-8

We employ the theory of evolving n-gons in the study of subdivision surfaces. We show that for subdivision schemes with small stencils the eige¬nanalysis of an evolving polygon, corresponding either to a face or to the 1-¬ring neighborhood of a verte... Read More about Evolutions of Polygons in the Study of Subdivision Surfaces.

Fast, large and controllable phase modulation using dual frequency liquid crystals (2004)
Journal Article
Kirby, A., & Love, G. (2004). Fast, large and controllable phase modulation using dual frequency liquid crystals. Optics Express, 12(7), 1470-1475. https://doi.org/10.1364/opex.12.001470

We report on a method for high speed, large stroke phase modulation using dual frequency control of liquid crystals. Our system uses an all-electronic feedback system in order to simplify the control. We show half wave phase modulations of ~120Hz wit... Read More about Fast, large and controllable phase modulation using dual frequency liquid crystals.

Dichotomies for classes of homomorphism problems involving unary functions (2004)
Journal Article
Feder, T., Madelaine, F., & Stewart, I. (2004). Dichotomies for classes of homomorphism problems involving unary functions. Theoretical Computer Science, 314(1-2), 1-43. https://doi.org/10.1016/j.tcs.2003.12.015

We study non-uniform constraint satisfaction problems where the underlying signature contains constant and function symbols as well as relation symbols. Amongst our results are the following. We establish a dichotomy result for the class of non-unifo... Read More about Dichotomies for classes of homomorphism problems involving unary functions.

Understanding service-oriented software (2004)
Journal Article
Gold, N., Knight, C., Mohan, A., & Munro, M. (2004). Understanding service-oriented software. IEEE Software, 21(2), 71-77. https://doi.org/10.1109/ms.2004.1270766

Service-oriented software is being hailed as the next revolutionary approach to software development. Service orientation allows organizations to rapidly and dynamically form new software applications to meet changing business needs, thus alleviating... Read More about Understanding service-oriented software.

Characterization of graphs with Hall number 2 (2004)
Journal Article
Eslachi, C., & Johnson, M. (2004). Characterization of graphs with Hall number 2. Journal of Graph Theory, 45(2), 81-100. https://doi.org/10.1002/jgt.10154

Hall's condition is a simple requirement that a graph G and list assignment L must satisfy if G is to have a proper L-colouring. The Hall number of G is the smallest integer m such that whenever the lists on the vertices each has size at least m and... Read More about Characterization of graphs with Hall number 2.

A sensitive optical polarimetric imaging technique for surface defects detection of aircraft turbine engines (2004)
Journal Article
Giakos, G., Fraiwan, L., Patnekar, N., Sumrain, S., Mertzios, G., & Periyathamby, S. (2004). A sensitive optical polarimetric imaging technique for surface defects detection of aircraft turbine engines. IEEE Transactions on Instrumentation and Measurement, 53(1), 216-222. https://doi.org/10.1109/tim.2003.821497

The design of an optical polarimetric imaging system, aimed to detect cracks or structural defects on the surface of rotating aircraft engine shafts, is presented: The experimental results, clearly indicate that high. signal-to-noise ratio signals ca... Read More about A sensitive optical polarimetric imaging technique for surface defects detection of aircraft turbine engines.