Skip to main content

Research Repository

Advanced Search

On the power of deep pushdown stacks (2009)
Journal Article
Arratia-Quesada, A., & Stewart, I. (2009). On the power of deep pushdown stacks. Acta Informatica, 46(7), 509-531. https://doi.org/10.1007/s00236-009-0103-x

Inspired by recent work of Meduna on deep pushdown automata, we consider the computational power of a class of basic program schemes, NPSDSs, based around assignments, while-loops and non-deterministic guessing but with access to a deep pushdown stac... Read More about On the power of deep pushdown stacks.

Logical and complexity-theoretic aspects of models of computation with restricted access to arrays (2009)
Journal Article
Stewart, I. (2009). Logical and complexity-theoretic aspects of models of computation with restricted access to arrays. Journal of Logic and Computation, 19(1), 217-242. https://doi.org/10.1093/logcom/exn025

We study a class of program schemes, NPSB, in which, aside from basic assignments, non-deterministic guessing and while loops, we have access to arrays; but where these arrays are binary write-once in that they are initialized to 'zero' and can only... Read More about Logical and complexity-theoretic aspects of models of computation with restricted access to arrays.

Program schemes, queues, the recursive spectrum and zero-one laws (2009)
Journal Article
Stewart, I. (2009). Program schemes, queues, the recursive spectrum and zero-one laws. Fundamenta Informaticae, 91(2), 411-435. https://doi.org/10.3233/fi-2009-0050

We prove that a very basic class of program schemes augmented with access to a queue and an additional numeric universe within which counting is permitted, so that the resulting class is denoted NPSQ$_+(1)$, is such that the class of problems accepte... Read More about Program schemes, queues, the recursive spectrum and zero-one laws.

Bipanconnectivity and bipancyclicity in k-ary n-cubes (2009)
Journal Article
Stewart, I., & Xiang, Y. (2009). Bipanconnectivity and bipancyclicity in k-ary n-cubes. IEEE Transactions on Parallel and Distributed Systems, 20(1), 25-33. https://doi.org/10.1109/tpds.2008.45

In this paper we give precise solutions to problems posed by Wang, An, Pan, Wang and Qu and by Hsieh, Lin and Huang. In particular, we show that Q_n^k is bipanconnected and edge-bipancyclic, when k ≥ 3 and n ≥ 2, and we also show that when k is odd,... Read More about Bipanconnectivity and bipancyclicity in k-ary n-cubes.

Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies (2008)
Journal Article
Madelaine, F., & Stewart, I. (2008). Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies. Discrete Mathematics, 308(18), 4144-4164. https://doi.org/10.1016/j.disc.2007.08.007

We improve upon the best known upper and lower bounds on the sizes of minimal feedback vertex sets in butterflies. Also, we construct new feedback vertex sets in grids so that for a large number of pairs $(n,m)$, the size of our feedback vertex set i... Read More about Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies.

Embedding long paths in k-ary n-cubes with faulty nodes and links (2008)
Journal Article
Stewart, I., & Xiang, Y. (2008). Embedding long paths in k-ary n-cubes with faulty nodes and links. IEEE Transactions on Parallel and Distributed Systems, 19(8), 1071-1085. https://doi.org/10.1109/tpds.2007.70787

Let $k \geq 4$ be even and let $n \geq 2$. Consider a faulty k-ary n-cube $Q_n^k$ in which the number of node faults $f_n$ and the number of link faults $f_e$ are such that $f_n + f_e \leq 2n-2$. We prove that given any two healthy nodes s and e of $... Read More about Embedding long paths in k-ary n-cubes with faulty nodes and links.

The computational complexity of the parallel knock-out problem (2008)
Journal Article
Broersma, H., Johnson, M., Paulusma, D., & Stewart, I. (2008). The computational complexity of the parallel knock-out problem. Theoretical Computer Science, 393(1-3), 182-195. https://doi.org/10.1016/j.tcs.2007.11.021

We consider computational complexity questions related to parallel knock-out schemes for graphs. In such schemes, in each round, each remaining vertex of a given graph eliminates exactly one of its neighbours. We show that the problem of whether, for... Read More about The computational complexity of the parallel knock-out problem.

Distributed algorithms for building Hamiltonian cycles in k-ary n-cubes and hypercubes with faulty links (2007)
Journal Article
Stewart, I. (2007). Distributed algorithms for building Hamiltonian cycles in k-ary n-cubes and hypercubes with faulty links. Journal of Interconnection Networks, 8(3), 253-284. https://doi.org/10.1142/s0219265907002016

We derive a sequential algorithm Find-Ham-Cycle with the following property. On input: k and n (specifying the k-ary n-cube Q(n,k); F, a set of at most 2n-2 faulty links; and v, a node of Q(n,k), the algorithm outputs nodes v+ and v- such that if Fin... Read More about Distributed algorithms for building Hamiltonian cycles in k-ary n-cubes and hypercubes with faulty links.

Constraint satisfaction, logic and forbidden patterns (2007)
Journal Article
Madelaine, F., & Stewart, I. (2007). Constraint satisfaction, logic and forbidden patterns. SIAM Journal on Computing, 37(1), 132-163. https://doi.org/10.1137/050634840

In the early nineties, Feder and Vardi attempted to find a large sub-class of NP which exhibits a dichotomy; that is, where every problem in the sub-class is either solvable in polynomial-time or NP-complete. Their studies resulted in a candidate cla... Read More about Constraint satisfaction, logic and forbidden patterns.

An infinite hierarchy in a class of polynomial-time program schemes (2006)
Journal Article
Gault, R., & Stewart, I. (2006). An infinite hierarchy in a class of polynomial-time program schemes. Theory of Computing Systems, 39(5), 753-783. https://doi.org/10.1007/s00224-005-1230-6

We define a class of program schemes RFDPS constructed around notions of forall-loops, repeat-loops, arrays and if-then-else instructions, and which take finite structures as inputs, and we examine the class of problems, denoted RFDPS also, accepted... Read More about An infinite hierarchy in a class of polynomial-time program schemes.

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.

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.

Program schemes, arrays, Lindström quantifiers and zero-one laws (2002)
Journal Article
Stewart, I. (2002). Program schemes, arrays, Lindström quantifiers and zero-one laws. Theoretical Computer Science, 275(1-2), 283-310. https://doi.org/10.1016/s0304-3975%2801%2900183-9

We characterize the class of problems accepted by a class of program schemes with arrays, NPSA, as the class of problems defined by the sentences of a logic formed by extending first-order logic with a particular uniform (or vectorized) sequence of L... Read More about Program schemes, arrays, Lindström quantifiers and zero-one laws.

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.

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.