Outputs (2)

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.