Skip to main content

Research Repository

Advanced Search

All Outputs (2741)

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.

Solving order constraints in logarithmic space (2003)
Presentation / Conference Contribution
Krokhin, A., & Larose, B. (2003). Solving order constraints in logarithmic space. In H. Alt, & M. Habib (Eds.), 20th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2003, 27 February-1 March 1 2003 ; proceedings (379-390). https://doi.org/10.1007/3-540-36494-3_34

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.

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.

Identifying Cause and Effect Relations between Events in Concurrent Event-Based Components (2003)
Presentation / Conference Contribution
Dias, M., & Richardson, D. J. (2003). Identifying Cause and Effect Relations between Events in Concurrent Event-Based Components. In 17th IEEE International Conference on Automated Software Engineering, ASE 2002, 23-27 September 2002, Edinburgh ; proceedings (245-248). https://doi.org/10.1109/ase.2002.1115021

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.

A novel multipath dispersion reduction technique based on controlled-polarization optical wireless link set-up (2003)
Presentation / Conference Contribution
Giakos, G., Patnekar, N., Sumrain, S., Fraiwan, L., Kumar, V., & Mertzios, G. (2003). A novel multipath dispersion reduction technique based on controlled-polarization optical wireless link set-up. In Instrumentation and Measurement Technology, 20th Annual Conference, IMTC '03, 20-22 May 2003, Colorado, USA ; proceedings (1622-1626). https://doi.org/10.1109/imtc.2003.1208024

The detection characteristics of an indoor-optical communication system, which utilizes infrared radiation as carrier has been explored and enhanced for telemedicine, and wireless local area network applications. The novelty of the presented techniqu... Read More about A novel multipath dispersion reduction technique based on controlled-polarization optical wireless link set-up.

Orientation and solvatochromism of dyes in liquid crystals (2003)
Journal Article
Palsson, L., Szablewski, M., Roberts, A., Masutani, A., Love, G., Cross, G., …Yasuda, A. (2003). Orientation and solvatochromism of dyes in liquid crystals. Molecular Crystals and Liquid Crystals, 402(1), 43-53. https://doi.org/10.1080/744816685

The orientation and solvatochromism of some dye molecules in a liquid crystal have been investigated. Interactions with the host and the structure of the dye molecule affect the macroscopic alignment of dichroic dye molecules in a liquid crystal: It... Read More about Orientation and solvatochromism of dyes in liquid crystals.

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.

Emulating MultiConjugate Turbulence (2002)
Presentation / Conference Contribution
Love, G. D., Clark, P., Dunlop, C. N., Kelly, T., Langloids, M., Myers, R. M., & Sharples, R. M. (2002). Emulating MultiConjugate Turbulence.

The refinability of the 4-point scheme. (2002)
Journal Article
Ivrissimtzis, I., Dodgson, N., Hassan, M., & Sabin, M. (2002). The refinability of the 4-point scheme. Computer Aided Geometric Design, 19(4), 235-238

Generic composition (2002)
Journal Article
Chen, Y. (2002). Generic composition. Formal aspects of computing (Internet), 14(2), 108-122. https://doi.org/10.1007/s001650200031

This paper presents a technique called {\em generic composition} to provide a uniform basis for modal operators, sequential composition, different kinds of parallel compositions and various healthiness conditions appearing in a variety of semantic th... Read More about Generic composition.