Outputs (66)

Fault-tolerant embeddings of Hamiltonian circuits in k-ary n-cubes (2002)
Journal Article
Ashir, Y., & Stewart, I. (2002). Fault-tolerant embeddings of Hamiltonian circuits in k-ary n-cubes. SIAM Journal on Discrete Mathematics, 15(3), 317-328. https://doi.org/10.1137/s0895480196311183

We consider the fault-tolerant capabilities of networks of processors whose underlying topology is that of the k-ary n-cube $Q_n^k$, where k > 2 and n > 1. In particular, given a copy of $Q_n^k$ where some of the inter-processor links may be faulty b... Read More about Fault-tolerant embeddings of Hamiltonian circuits in k-ary n-cubes.

A generic greedy algorithm, partially-ordered graphs and NP-completeness (2001)
Presentation / Conference Contribution
Puricella, A., & Stewart, I. (2001, June). A generic greedy algorithm, partially-ordered graphs and NP-completeness. Presented at 27th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2001), Rostock, Germany

Let π be any fixed polynomial-time testable, non-trivial, hereditary property of graphs. Suppose that the vertices of a graph G are not necessarily linearly ordered but partially ordered, where we think of this partial order as a collection of (possi... Read More about A generic greedy algorithm, partially-ordered graphs and NP-completeness.

On a hierarchy involving transitive closure logic and existential second-order quantification (2001)
Journal Article
Gault, R., & Stewart, I. (2001). On a hierarchy involving transitive closure logic and existential second-order quantification. Logic Journal of the IGPL, 9(6), 769-780. https://doi.org/10.1093/jigpal/9.6.769

We study a hierarchy of logics where each formula of each logic in the hierarchy consists of a formula of a certain fragment of transitive closure logic prefixed with an existentially quantified tuple of unary relation symbols. By playing an Ehrenfeu... Read More about On a hierarchy involving transitive closure logic and existential second-order quantification.

On the power of built-in relations in certain classes of program schemes (1999)
Journal Article
Chauhan, S., & Stewart, I. (1999). On the power of built-in relations in certain classes of program schemes. Information Processing Letters, 69(2), 77-82. https://doi.org/10.1016/s0020-0190%2898%2900196-3

We completely classify the relative expressibilities of the program schemes of NPS augmented with the built-in relations: linear order; addition; multiplication; and BIT. We employ pebble games allied with some number theory.

Hierarchies in classes of program schemes (1999)
Journal Article
Arratia-Quesada, A., Chauhan, S., & Stewart, I. (1999). Hierarchies in classes of program schemes. Journal of Logic and Computation, 9(6), 915-957. https://doi.org/10.1093/logcom/9.6.915

We begin by proving that the class of problems accepted by the program schemes of NPS is exactly the class of problems defined by the sentences of transitive closure logic (program schemes of NPS are obtained by generalizing basic non-deterministic w... Read More about Hierarchies in classes of program schemes.

A perspective on Lindström quantifiers and oracles (1999)
Book Chapter
Stewart, I. (1999). A perspective on Lindström quantifiers and oracles. In J. Väänänen (Ed.), Generalized quantifiers and computation : 9th European Summer School in Logic, Language, and Information ESSLLI’97 Workshop, 11-22 August 1997, Aix-en-Provence, France ; revised lectures (51-71). Springer Verlag. https://doi.org/10.1007/3-540-46583-9_3

This paper presents a perspective on the relationship between Lindström quantifiers in model theory and oracle computations in complexity theory. We do not study this relationship here in full generality (indeed, there is much more work to do in orde... Read More about A perspective on Lindström quantifiers and oracles.