Showing 1–49 of 49 results for author: Maher, J

Which are the True Defeasible Logics?

Authors: Michael J. Maher

Abstract: The class of defeasible logics is only vaguely defined -- it is defined by a few exemplars and the general idea of efficient reasoning with defeasible rules. The recent definition of the defeasible logic $DL(\partial_{||})$ introduced new features to such logics, which have repercussions that we explore. In particular, we define a class of logics that accommodates the new logic while retaining the… ▽ More The class of defeasible logics is only vaguely defined -- it is defined by a few exemplars and the general idea of efficient reasoning with defeasible rules. The recent definition of the defeasible logic $DL(\partial_{||})$ introduced new features to such logics, which have repercussions that we explore. In particular, we define a class of logics that accommodates the new logic while retaining the traditional properties of defeasible logics. △ Less

Submitted 29 May, 2024; originally announced May 2024.

MSC Class: 03B70; 03B60; 68T27 ACM Class: I.2.3; I.2.4; F.4.1

Banach-Tarski Embeddings and Transformers

Authors: Joshua Maher

Abstract: We introduce a new construction of embeddings of arbitrary recursive data structures into high dimensional vectors. These embeddings provide an interpretable model for the latent state vectors of transformers. We demonstrate that these embeddings can be decoded to the original data structure when the embedding dimension is sufficiently large. This decoding algorithm has a natural implementation as… ▽ More We introduce a new construction of embeddings of arbitrary recursive data structures into high dimensional vectors. These embeddings provide an interpretable model for the latent state vectors of transformers. We demonstrate that these embeddings can be decoded to the original data structure when the embedding dimension is sufficiently large. This decoding algorithm has a natural implementation as a transformer. We also show that these embedding vectors can be manipulated directly to perform computations on the underlying data without decoding. As an example we present an algorithm that constructs the embedded parse tree of an embedded token sequence using only vector operations in embedding space. △ Less

Submitted 21 November, 2023; v1 submitted 15 November, 2023; originally announced November 2023.

Comments: 22 pages, 7 figures. v2: Fixed order of matrix multiplication in section 2.4

Enabling Research through the SCIP Optimization Suite 8.0

Authors: Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Oliver Gaul, Gerald Gamrath, Ambros Gleixner, Leona Gottwald, Christoph Graczyk, Katrin Halbig, Alexander Hoen, Christopher Hojny, Rolf van der Hulst, Thorsten Koch, Marco Lübbecke, Stephen J. Maher, Frederic Matter, Erik Mühmer, Benjamin Müller, Marc E. Pfetsch, Daniel Rehfeldt, Steffan Schlein , et al. (10 additional authors not shown)

Abstract: The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. The focus of this paper is on the role of the SCIP Optimization Suite in supporting research. SCIP's main design principles are discussed, followed by a presentation of the latest performance improvements and developments in version… ▽ More The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. The focus of this paper is on the role of the SCIP Optimization Suite in supporting research. SCIP's main design principles are discussed, followed by a presentation of the latest performance improvements and developments in version 8.0, which serve both as examples of SCIP's application as a research tool and as a platform for further developments. Further, the paper gives an overview of interfaces to other programming and modeling languages, new features that expand the possibilities for user interaction with the framework, and the latest developments in several extensions built upon SCIP. △ Less

Submitted 13 March, 2023; originally announced March 2023.

Comments: arXiv admin note: substantial text overlap with arXiv:2112.08872

MSC Class: 90C05; 90C10; 90C11; 90C30; 90C90; 65Y05

SPRINT: A fast, new software tool for reconstructing the evolutionary past of polyploid datasets

Authors: Liam J. Maher, Taoyang Wu, Katharina T. Huber

Abstract: Polyploidization is an important evolutionary process which affects organisms ranging from plants to fish and fungi. The signal left behind by it is in the form of a species' ploidy level (number of complete chromosome sets found in a cell) which is inherently non-treelike. Currently available tools for reconstructing the evolutionary past of a polyploid dataset generally start with a multi-labell… ▽ More Polyploidization is an important evolutionary process which affects organisms ranging from plants to fish and fungi. The signal left behind by it is in the form of a species' ploidy level (number of complete chromosome sets found in a cell) which is inherently non-treelike. Currently available tools for reconstructing the evolutionary past of a polyploid dataset generally start with a multi-labelled tree obtained for a dataset of interest and then derive a (phylogenetic) network from that tree in some way that reflects that past by interpreting the networks's vertices of indegree at least two as polyploidization events. Since obtaining such a tree can be computationally expensive it is paramount to have alternative approaches available that allow one to shed light into the reticulate evolutionary past of a polyploid dataset. SPRINT aims to reconstruct the evolutionary past of a polyploid dataset in terms of a binary network which realises the dataset's ploidy profile (vector of ploidy levels of the dataset's taxa) and requires the fewest number of polyploidization events. It does this by representing the ploidy level of a species x in terms of the number of directed paths from the root of the network to the leaf of the network labelled by x. SPRINT is distributed on GitHub: https://github.com/lmaher1/SPRINT. △ Less

Submitted 9 November, 2022; originally announced November 2022.

Comments: 4 pages, 2 figures

Autopolyploidy, allopolyploidy, and phylogenetic networks with horizontal arcs

Authors: Katharina T. Huber, Liam J. Maher

Abstract: Polyploidization is an evolutionary process by which a species acquires multiple copies of its complete set of chromosomes. The reticulate nature of the signal left behind by it means that phylogenetic networks offer themselves as a framework to reconstruct the evolutionary past of species affected by it. The main strategy for doing this is to first construct a so called multiple-labelled tree and… ▽ More Polyploidization is an evolutionary process by which a species acquires multiple copies of its complete set of chromosomes. The reticulate nature of the signal left behind by it means that phylogenetic networks offer themselves as a framework to reconstruct the evolutionary past of species affected by it. The main strategy for doing this is to first construct a so called multiple-labelled tree and to then somehow derive such a network from it. The following question therefore arises: How much can be said about that past if such a tree is not readily available? By viewing a polyploid dataset as a certain vector which we call a ploidy (level) profile we show that, among other results, there always exists a phylogenetic network in the form of a beaded phylogenetic tree with additional arcs that realizes a given ploidy profile. Intriguingly, the two end vertices of almost all of these additional arcs can be interpreted as having co-existed in time thereby adding biological realism to our network, a feature that is, in general, not enjoyed by phylogenetic networks. In addition, we show that our network may be viewed as a generator of ploidy profile space, a novel concept similar to phylogenetic tree space that we introduce to be able to compare phylogenetic networks that realize one and the same ploidy profile. We illustrate our findings in terms of a publicly available Viola dataset. △ Less

Submitted 19 February, 2023; v1 submitted 11 October, 2022; originally announced October 2022.

Comments: 26 pages, 9 figures, 38 citations

The SCIP Optimization Suite 8.0

Authors: Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Oliver Gaul, Gerald Gamrath, Ambros Gleixner, Leona Gottwald, Christoph Graczyk, Katrin Halbig, Alexander Hoen, Christopher Hojny, Rolf van der Hulst, Thorsten Koch, Marco Lübbecke, Stephen J. Maher, Frederic Matter, Erik Mühmer, Benjamin Müller, Marc E. Pfetsch, Daniel Rehfeldt, Steffan Schlein , et al. (10 additional authors not shown)

Abstract: The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 8.0 of the SCIP Optimization Suite. Major updates in SCIP include improvements in symmetry handling and decomposition algorithms, new cutting planes, a new plugin… ▽ More The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 8.0 of the SCIP Optimization Suite. Major updates in SCIP include improvements in symmetry handling and decomposition algorithms, new cutting planes, a new plugin type for cut selection, and a complete rework of the way nonlinear constraints are handled. Additionally, SCIP 8.0 now supports interfaces for Julia as well as Matlab. Further, UG now includes a unified framework to parallelize all solvers, a utility to analyze computational experiments has been added to GCG, dual solutions can be postsolved by PaPILO, new heuristics and presolving methods were added to SCIP-SDP, and additional problem classes and major performance improvements are available in SCIP-Jack. △ Less

Submitted 16 December, 2021; originally announced December 2021.

Comments: 114 pages, 8 figures

MSC Class: 90C05; 90C10; 90C11; 90C30; 90C90; 65Y05

Approximating Defeasible Logics to Improve Scalability

Authors: Michael J. Maher

Abstract: Defeasible rules are used in providing computable representations of legal documents and, more recently, have been suggested as a basis for explainable AI. Such applications draw attention to the scalability of implementations. The defeasible logic $DL(\partial_{||})$ was introduced as a more scalable alternative to $DL(\partial)$, which is better known. In this paper we consider the use of (imple… ▽ More Defeasible rules are used in providing computable representations of legal documents and, more recently, have been suggested as a basis for explainable AI. Such applications draw attention to the scalability of implementations. The defeasible logic $DL(\partial_{||})$ was introduced as a more scalable alternative to $DL(\partial)$, which is better known. In this paper we consider the use of (implementations of) $DL(\partial_{||})$ as a computational aid to computing conclusions in $DL(\partial)$ and other defeasible logics, rather than as an alternative to $DL(\partial)$. We identify conditions under which $DL(\partial_{||})$ can be substituted for $DL(\partial)$ with no change to the conclusions drawn, and conditions under which $DL(\partial_{||})$ can be used to draw some valid conclusions, leaving the remainder to be drawn by $DL(\partial)$. △ Less

Submitted 11 August, 2021; originally announced August 2021.

Comments: This is a technical report from the Reasoning Research Institute

MSC Class: 03B70; 03B60; 03B53 ACM Class: I.2.3; I.2.4; F.4.1

Defeasible Reasoning via Datalog$^\neg$

Authors: Michael J. Maher

Abstract: We address the problem of compiling defeasible theories to Datalog$^\neg$ programs. We prove the correctness of this compilation, for the defeasible logic $DL(\partial_{||})$, but the techniques we use apply to many other defeasible logics. Structural properties of $DL(\partial_{||})$ are identified that support efficient implementation and/or approximation of the conclusions of defeasible theorie… ▽ More We address the problem of compiling defeasible theories to Datalog$^\neg$ programs. We prove the correctness of this compilation, for the defeasible logic $DL(\partial_{||})$, but the techniques we use apply to many other defeasible logics. Structural properties of $DL(\partial_{||})$ are identified that support efficient implementation and/or approximation of the conclusions of defeasible theories in the logic, compared with other defeasible logics. We also use previously well-studied structural properties of logic programs to adapt to incomplete Datalog$^\neg$ implementations. △ Less

Submitted 21 June, 2021; originally announced June 2021.

Comments: Under consideration in Theory and Practice of Logic Programming (TPLP)

MSC Class: 03B70 (Primary) 03B60; 03B53 (Secondary) ACM Class: I.2.3; F.4.1; I.2.2; I.2.4

Journal ref: Theory and Practice of Logic Programming 23 (5), 986-1028, 2021

Assessing the Effectiveness of (Parallel) Branch-and-bound Algorithms

Authors: Stephen J. Maher, Ted K. Ralphs, Yuji Shinano

Abstract: Empirical studies are fundamental in assessing the effectiveness of implementations of branch-and-bound algorithms. The complexity of such implementations makes empirical study difficult for a wide variety of reasons. Various attempts have been made to develop and codify a set of standard techniques for the assessment of optimization algorithms and their software implementations; however, most pre… ▽ More Empirical studies are fundamental in assessing the effectiveness of implementations of branch-and-bound algorithms. The complexity of such implementations makes empirical study difficult for a wide variety of reasons. Various attempts have been made to develop and codify a set of standard techniques for the assessment of optimization algorithms and their software implementations; however, most previous work has been focused on classical sequential algorithms. Since parallel computation has become increasingly mainstream, it is necessary to re-examine and modernize these practices. In this paper, we propose a framework for assessment based on the notion that \emph{resource consumption} is at the heart of what we generally refer to as the "effectiveness" of an implementation. The proposed framework carefully distinguishes between an implementation's baseline efficiency, the efficacy with which it utilizes a fixed allocation of resources, and its scalability, a measure of how the efficiency changes as resources (typically additional computing cores) are added or removed. Efficiency is typically applied to sequential implementations, whereas scalability is applied to parallel implementations. Efficiency and scalability are both important contributors in determining the overall effectiveness of a given parallel implementation, but the goal of improved efficiency is often at odds with the goal of improved scalability. Within the proposed framework, we review the challenges to effective evaluation and discuss the strengths and weaknesses of existing methods of assessment. △ Less

Submitted 18 April, 2021; originally announced April 2021.

Report number: Laboratory for Computational Optimization Research @ Lehigh (COR@L) Technical Report 19T-017 MSC Class: 90C57; 68W10; 65Y20; 68Q25

Relative Expressiveness of Defeasible Logics II

Authors: Michael J. Maher

Abstract: (Maher 2012) introduced an approach for relative expressiveness of defeasible logics, and two notions of relative expressiveness were investigated. Using the first of these definitions of relative expressiveness, we show that all the defeasible logics in the DL framework are equally expressive under this formulation of relative expressiveness. The second formulation of relative expressiveness is s… ▽ More (Maher 2012) introduced an approach for relative expressiveness of defeasible logics, and two notions of relative expressiveness were investigated. Using the first of these definitions of relative expressiveness, we show that all the defeasible logics in the DL framework are equally expressive under this formulation of relative expressiveness. The second formulation of relative expressiveness is stronger than the first. However, we show that logics incorporating individual defeat are equally expressive as the corresponding logics with team defeat. Thus the only differences in expressiveness of logics in DL arise from differences in how ambiguity is handled. This completes the study of relative expressiveness in DL begun in \cite{Maher12}. △ Less

Submitted 21 February, 2021; originally announced February 2021.

Comments: Includes extensive appendix

ACM Class: I.2.4

Journal ref: Theory and Practice of Logic Programming 13 (2013) 579-592

On Signings and the Well-Founded Semantics

Authors: Michael J. Maher

Abstract: In this note, we use Kunen's notion of a signing to establish two theorems about the well-founded semantics of logic programs, in the case where we are interested in only (say) the positive literals of a predicate $p$ that are consequences of the program. The first theorem identifies a class of programs for which the well-founded and Fitting semantics coincide for the positive part of $p$. The sec… ▽ More In this note, we use Kunen's notion of a signing to establish two theorems about the well-founded semantics of logic programs, in the case where we are interested in only (say) the positive literals of a predicate $p$ that are consequences of the program. The first theorem identifies a class of programs for which the well-founded and Fitting semantics coincide for the positive part of $p$. The second theorem shows that if a program has a signing then computing the positive part of $p$ under the well-founded semantics requires the computation of only one part of each predicate. This theorem suggests an analysis for query-answering under the well-founded semantics. In the process of proving these results, we use an alternative formulation of the well-founded semantics of logic programs, which might be of independent interest. Under consideration in Theory and Practice of Logic Programming (TPLP) △ Less

Submitted 14 February, 2021; v1 submitted 12 February, 2021; originally announced February 2021.

Comments: Under consideration in Theory and Practice of Logic Programming (TPLP)

MSC Class: 68N17; 03B70 ACM Class: F.3.2; F.4.1; H.2.3

Journal ref: Theory and Practice of Logic Programming 22 (2022) 115-127

The hybrid number of a ploidy profile

Authors: Katharina T. Huber, Liam J. Maher

Abstract: Polyploidization, whereby an organism inherits multiple copies of the genome of their parents, is an important evolutionary event that has been observed in plants and animals. One way to study such events is in terms of the ploidy number of the species that make up a dataset of interest. It is therefore natural to ask: How much information about the evolutionary past of the set of species that for… ▽ More Polyploidization, whereby an organism inherits multiple copies of the genome of their parents, is an important evolutionary event that has been observed in plants and animals. One way to study such events is in terms of the ploidy number of the species that make up a dataset of interest. It is therefore natural to ask: How much information about the evolutionary past of the set of species that form a dataset can be gleaned from the ploidy numbers of the species? To help answer this question, we introduce and study the novel concept of a ploidy profile which allows us to formalize it in terms of a multiplicity vector indexed by the species the dataset is comprised of. Using the framework of a phylogenetic network, we present a closed formula for computing the hybrid number (i.e. the minimal number of polyploidization events required to explain a ploidy profile) of a large class of ploidy profiles. This formula relies on the construction of a certain phylogenetic network from the simplification sequence of a ploidy profile and the hybrid number of the ploidy profile with which this construction is initialized. Both of them can be computed easily in case the ploidy numbers that make up the ploidy profile are not too large. To help illustrate the applicability of our approach, we apply it to a simplified version of a publicly available Viola dataset. △ Less

Submitted 11 August, 2022; v1 submitted 26 January, 2021; originally announced January 2021.

Comments: 27 pages, 11 figures, 26 citations

Identifying opinion-based groups from survey data: a bipartite network approach

Authors: Pádraig MacCarron, Paul J. Maher, Michael Quayle

Abstract: A survey can be represented by a bipartite network as it has two types of nodes, participants and items in which participants can only interact with items. We introduce an agreement threshold to take a minimal projection of the participants linked by shared responses in order to identify opinion-based groups. We show that in American National Election Studies-data, this can identify polarisation a… ▽ More A survey can be represented by a bipartite network as it has two types of nodes, participants and items in which participants can only interact with items. We introduce an agreement threshold to take a minimal projection of the participants linked by shared responses in order to identify opinion-based groups. We show that in American National Election Studies-data, this can identify polarisation along political attitudes. We also take a projection of attitudes that are linked by how participants respond to them. This can be used to show which attitudes are commonly held together in different countries or communities. △ Less

Submitted 17 December, 2020; originally announced December 2020.

Comments: 11 pages, 6 figures

MSC Class: 90C35

Quotients of the curve complex

Authors: Joseph Maher, Hidetoshi Masai, Saul Schleimer

Abstract: We consider three kinds of quotients of the curve complex which are obtained by coning off uniformly quasi-convex subspaces: symmetric curve sets, non-maximal train track sets, and compression body disc sets. We show that the actions of the mapping class group on those quotients are strongly WPD, which implies that the actions are non-elementary and those quotients are of infinite diameter. We consider three kinds of quotients of the curve complex which are obtained by coning off uniformly quasi-convex subspaces: symmetric curve sets, non-maximal train track sets, and compression body disc sets. We show that the actions of the mapping class group on those quotients are strongly WPD, which implies that the actions are non-elementary and those quotients are of infinite diameter. △ Less

Submitted 26 October, 2020; originally announced October 2020.

Comments: 26 pages, 6 figures

MSC Class: 37E30; 20F65; 57M50

Corruption and Audit in Strategic Argumentation

Authors: Michael J. Maher

Abstract: Strategic argumentation provides a simple model of disputation and negotiation among agents. Although agents might be expected to act in our best interests, there is little that enforces such behaviour. (Maher, 2016) introduced a model of corruption and resistance to corruption within strategic argumentation. In this paper we identify corrupt behaviours that are not detected in that formulation. W… ▽ More Strategic argumentation provides a simple model of disputation and negotiation among agents. Although agents might be expected to act in our best interests, there is little that enforces such behaviour. (Maher, 2016) introduced a model of corruption and resistance to corruption within strategic argumentation. In this paper we identify corrupt behaviours that are not detected in that formulation. We strengthen the model to detect such behaviours, and show that, under the strengthened model, all the strategic aims in (Maher, 2016) are resistant to corruption. △ Less

Submitted 30 August, 2020; originally announced August 2020.

Comments: Reasoning Research Institute technical report, 2017

MSC Class: 68T30; 68T35; 68T42 ACM Class: I.2.4; F.2.2

A lemma on closures and its application to modularity in logic programming semantics

Authors: Michael J. Maher

Abstract: This note points out a lemma on closures of monotonic increasing functions and shows how it is applicable to decomposition and modularity for semantics defined as the least fixedpoint of some monotonic function. In particular it applies to numerous semantics of logic programs. An appendix addresses the fixedpoints of (possibly non-monotonic) functions that are sandwiched between functions with the… ▽ More This note points out a lemma on closures of monotonic increasing functions and shows how it is applicable to decomposition and modularity for semantics defined as the least fixedpoint of some monotonic function. In particular it applies to numerous semantics of logic programs. An appendix addresses the fixedpoints of (possibly non-monotonic) functions that are sandwiched between functions with the same fixedpoints. △ Less

Submitted 3 August, 2020; originally announced August 2020.

Comments: 12 pages

MSC Class: 68N17 ACM Class: D.3.1; F.3.1

Rethinking Defeasible Reasoning: A Scalable Approach

Authors: Michael J. Maher, Ilias Tachmazidis, Grigoris Antoniou, Stephen Wade, Long Cheng

Abstract: Recent technological advances have led to unprecedented amounts of generated data that originate from the Web, sensor networks and social media. Analytics in terms of defeasible reasoning - for example for decision making - could provide richer knowledge of the underlying domain. Traditionally, defeasible reasoning has focused on complex knowledge structures over small to medium amounts of data, b… ▽ More Recent technological advances have led to unprecedented amounts of generated data that originate from the Web, sensor networks and social media. Analytics in terms of defeasible reasoning - for example for decision making - could provide richer knowledge of the underlying domain. Traditionally, defeasible reasoning has focused on complex knowledge structures over small to medium amounts of data, but recent research efforts have attempted to parallelize the reasoning process over theories with large numbers of facts. Such work has shown that traditional defeasible logics come with overheads that limit scalability. In this work, we design a new logic for defeasible reasoning, thus ensuring scalability by design. We establish several properties of the logic, including its relation to existing defeasible logics. Our experimental results indicate that our approach is indeed scalable and defeasible reasoning can be applied to billions of facts. △ Less

Submitted 2 January, 2020; originally announced January 2020.

Comments: Under consideration in Theory and Practice of Logic Programming (TPLP)

Journal ref: Theory and Practice of Logic Programming 20 (2020) 552-586

Agreement Threshold on Axelrod's model of Cultural Dissemination

Authors: Pádraig Mac Carron, Paul J. Maher, Susan Fennell, Kevin Burke, James P. Gleeson, Kevin Durrheim, Mike Quayle

Abstract: Shared opinions are an important feature in the formation of social groups. In this paper, we use the Axelrod model of cultural dissemination to represent opinion-based groups. In the Axelrod model, each agent has a set of features which each holds one of a set of nominally related traits. Survey data, for example, has a similar structure, where each participant answers each of a set of items with… ▽ More Shared opinions are an important feature in the formation of social groups. In this paper, we use the Axelrod model of cultural dissemination to represent opinion-based groups. In the Axelrod model, each agent has a set of features which each holds one of a set of nominally related traits. Survey data, for example, has a similar structure, where each participant answers each of a set of items with responses from a fixed list. We present an alternative method of displaying the Axelrod model by representing it as a bipartite graph, i.e., participants and their responses as separate nodes. This allows us to see which feature-trait combinations are selected in the final state. This visualisation is particularly useful when representing survey data as it illustrates the co-evolution of cultures and opinion-based groups in Axelrod's model of cultural diffusion. We also present a modification to the Axelrod model. A standard finding of the Axelrod model with many features is for all agents to fully agree in one cluster. We introduce an agreement threshold and allow nodes to interact only with those neighbours who are within this threshold (i.e., those with similar opinions) rather than those with any opinion. This method reliably yields a large number of clusters for small agreement thresholds and, importantly, does not limit to single cluster when the number of features grows large. This potentially provides a method for modelling opinion-based groups where as opinions are added, the number of clusters increase. △ Less

Submitted 25 May, 2020; v1 submitted 13 November, 2019; originally announced November 2019.

Comments: 9 pages, 8 figures

MSC Class: 90C35

Journal ref: PLOS One 2020

Random trees in the boundary of Outer space

Authors: Ilya Kapovich, Joseph Maher, Catherine Pfaff, Samuel J. Taylor

Abstract: We prove that for the harmonic measure associated to a random walk on Out$(F_r)$ satisfying some mild conditions, a typical tree in the boundary of Outer space is trivalent and nongeometric. This answers a question of M. Bestvina. We prove that for the harmonic measure associated to a random walk on Out$(F_r)$ satisfying some mild conditions, a typical tree in the boundary of Outer space is trivalent and nongeometric. This answers a question of M. Bestvina. △ Less

Submitted 6 March, 2021; v1 submitted 22 April, 2019; originally announced April 2019.

Comments: 28 pages; minor typesetting issues corrected from the previous update. Accepted for publication in Geometry & Topology

MSC Class: 20F65 (Primary); 57M; 37B; 37D (Secondary)

Journal ref: Geom. Topol. 26 (2022) 127-162

Generating Hard Instances for Robust Combinatorial Optimization

Authors: Marc Goerigk, Stephen J. Maher

Abstract: While research in robust optimization has attracted considerable interest over the last decades, its algorithmic development has been hindered by several factors. One of them is a missing set of benchmark instances that make algorithm performance better comparable, and makes reproducing instances unnecessary. Such a benchmark set should contain hard instances in particular, but so far, the standar… ▽ More While research in robust optimization has attracted considerable interest over the last decades, its algorithmic development has been hindered by several factors. One of them is a missing set of benchmark instances that make algorithm performance better comparable, and makes reproducing instances unnecessary. Such a benchmark set should contain hard instances in particular, but so far, the standard approach to produce instances has been to sample values randomly from a uniform distribution. In this paper we introduce a new method to produce hard instances for min-max combinatorial optimization problems, which is based on an optimization model itself. Our approach does not make any assumptions on the problem structure and can thus be applied to any combinatorial problem. Using the Selection and Traveling Salesman problems as examples, we show that it is possible to produce instances which are up to 500 times harder to solve for a mixed-integer programming solver than the current state-of-the-art instances. △ Less

Submitted 8 February, 2019; v1 submitted 2 November, 2018; originally announced November 2018.

Random walks, WPD actions, and the Cremona group

Authors: Joseph Maher, Giulio Tiozzo

Abstract: We study random walks on groups of isometries of non-proper delta-hyperbolic spaces under the assumption that at least one element in the group satisfies Bestvina-Fujiwara's WPD condition. We show that in this case typical elements are WPD, and the Poisson boundary coincides with the Gromov boundary. Moreover, we show that the random walk satisfies a form of asymptotic acylindricality, and we use… ▽ More We study random walks on groups of isometries of non-proper delta-hyperbolic spaces under the assumption that at least one element in the group satisfies Bestvina-Fujiwara's WPD condition. We show that in this case typical elements are WPD, and the Poisson boundary coincides with the Gromov boundary. Moreover, we show that the random walk satisfies a form of asymptotic acylindricality, and we use this to show that the normal closure of random elements yields almost surely infinitely many different normal subgroups. Moreover, the probability that the normal closure is free tends to 1 if and only if the maximal normal subgroup coincides with the center of the group. We apply such techniques to the Cremona group, thus obtaining that the dynamical degree of random Cremona transformations grows exponentially fast, producing many different normal subgroups, and identifying the Poisson boundary. We also give a new identification of the Poisson boundary of Out(F_n). Our methods give bounds on the rates of convergence for these results. △ Less

Submitted 5 January, 2021; v1 submitted 26 July, 2018; originally announced July 2018.

Comments: 54 pages, 8 figures. Various revisions; improved rate of decay to exponential

MSC Class: 60G50; 20F67; 57M60

Random outer automorphisms of free groups: Attracting trees and their singularity structures

Authors: Ilya Kapovich, Joseph Maher, Catherine Pfaff, Samuel J. Taylor

Abstract: We prove that a "random" free group outer automorphism is an ageometric fully irreducible outer automorphism whose ideal Whitehead graph is a union of triangles. In particular, we show that its attracting (and repelling) tree is a nongeometric $\mathbb R$-tree all of whose branch points are trivalent We prove that a "random" free group outer automorphism is an ageometric fully irreducible outer automorphism whose ideal Whitehead graph is a union of triangles. In particular, we show that its attracting (and repelling) tree is a nongeometric $\mathbb R$-tree all of whose branch points are trivalent △ Less

Submitted 31 May, 2018; originally announced May 2018.

Comments: 27 pages comments are welcome!

MSC Class: Primary 20F65; Secondary 57M; 37B; 37D

The compression body graph has infinite diameter

Authors: Joseph Maher, Saul Schleimer

Abstract: We show that the compression body graph has infinite diameter. We show that the compression body graph has infinite diameter. △ Less

Submitted 20 July, 2020; v1 submitted 15 March, 2018; originally announced March 2018.

Comments: 34 pages, 14 figures, v2: minor changes, updated references

MSC Class: 37E30; 20F65; 57M50

Journal ref: Algebr. Geom. Topol. 21 (2021) 1817-1856

Morse functions to graphs and topological complexity for hyperbolic 3-manifolds

Authors: Diane Hoffoss, Joseph Maher

Abstract: Scharlemann and Thompson define the width of a 3-manifold M as a notion of complexity based on the topology of M. Their original definition had the property that the adjacency relation on handles gave a linear order on handles, but here we consider a more general definition due to Saito, Scharlemann and Schultens, in which the adjacency relation on handles may give an arbitrary graph. We show that… ▽ More Scharlemann and Thompson define the width of a 3-manifold M as a notion of complexity based on the topology of M. Their original definition had the property that the adjacency relation on handles gave a linear order on handles, but here we consider a more general definition due to Saito, Scharlemann and Schultens, in which the adjacency relation on handles may give an arbitrary graph. We show that for compact hyperbolic 3-manifolds, this is linearly related to a notion of metric complexity, based on the areas of level sets of Morse functions to graphs, which we call Gromov area. △ Less

Submitted 10 August, 2017; originally announced August 2017.

Comments: 21 pages, 1 figure. arXiv admin note: text overlap with arXiv:1503.08521

Annotated Defeasible Logic

Authors: Guido Governatori, Michael J. Maher

Abstract: Defeasible logics provide several linguistic features to support the expression of defeasible knowledge. There is also a wide variety of such logics, expressing different intuitions about defeasible reasoning. However, the logics can only combine in trivial ways. This limits their usefulness in contexts where different intuitions are at play in different aspects of a problem. In particular, in som… ▽ More Defeasible logics provide several linguistic features to support the expression of defeasible knowledge. There is also a wide variety of such logics, expressing different intuitions about defeasible reasoning. However, the logics can only combine in trivial ways. This limits their usefulness in contexts where different intuitions are at play in different aspects of a problem. In particular, in some legal settings, different actors have different burdens of proof, which might be expressed as reasoning in different defeasible logics. In this paper, we introduce annotated defeasible logic as a flexible formalism permitting multiple forms of defeasibility, and establish some properties of the formalism. This paper is under consideration for acceptance in Theory and Practice of Logic Programming. △ Less

Submitted 15 July, 2017; originally announced July 2017.

Comments: Paper presented at the 33nd International Conference on Logic Programming (ICLP 2017), Melbourne, Australia, August 28 to September 1, 2017 16 pages, LaTeX

Journal ref: Theory and Practice of Logic Programming 17 (5-6), 819--836, 2017

Recurrence of quadratic differentials for harmonic measure

Authors: Vaibhav Gadre, Joseph Maher

Abstract: We consider random walks on the mapping class group that have finite first moment with respect to the word metric, whose support generates a non-elementary subgroup and contains a pseudo-Anosov map whose invariant Teichmuller geodesic is in the principal stratum of quadratic differentials. We show that a Teichmuller geodesic typical with respect to the harmonic measure for such random walks, is re… ▽ More We consider random walks on the mapping class group that have finite first moment with respect to the word metric, whose support generates a non-elementary subgroup and contains a pseudo-Anosov map whose invariant Teichmuller geodesic is in the principal stratum of quadratic differentials. We show that a Teichmuller geodesic typical with respect to the harmonic measure for such random walks, is recurrent to the thick part of the principal stratum. As a consequence, the vertical and horizontal foliations of such a random Teichmuller geodesic have no saddle connections. △ Less

Submitted 6 June, 2017; originally announced June 2017.

Comments: 5 pages

Journal ref: Math. Proc. Camb. Phil. Soc. 169 (2020) 299-305

Contractibility for Open Global Constraints

Authors: Michael J. Maher

Abstract: Open forms of global constraints allow the addition of new variables to an argument during the execution of a constraint program. Such forms are needed for difficult constraint programming problems where problem construction and problem solving are interleaved, and fit naturally within constraint logic programming. However, in general, filtering that is sound for a global constraint can be unsound… ▽ More Open forms of global constraints allow the addition of new variables to an argument during the execution of a constraint program. Such forms are needed for difficult constraint programming problems where problem construction and problem solving are interleaved, and fit naturally within constraint logic programming. However, in general, filtering that is sound for a global constraint can be unsound when the constraint is open. This paper provides a simple characterization, called contractibility, of the constraints where filtering remains sound when the constraint is open. With this characterization we can easily determine whether a constraint has this property or not. In the latter case, we can use it to derive a contractible approximation to the constraint. We demonstrate this work on both hard and soft constraints. In the process, we formulate two general classes of soft constraints. △ Less

Submitted 25 February, 2017; originally announced February 2017.

Comments: Under consideration in Theory and Practice of Logic Programming (TPLP)

Journal ref: Theory and Practice of Logic Programming 17(4), 365--407, 2017

Random subgroups of acylindrically hyperbolic groups and hyperbolic embeddings

Authors: Joseph Maher, Alessandro Sisto

Abstract: Let G be an acylindrically hyperbolic group. We consider a random subgroup H in G, generated by a finite collection of independent random walks. We show that, with asymptotic probability one, such a random subgroup H of G is a free group, and the semidirect product of H acting on E(G) is hyperbolically embedded in G, where E(G) is the unique maximal finite normal subgroup of G. Let G be an acylindrically hyperbolic group. We consider a random subgroup H in G, generated by a finite collection of independent random walks. We show that, with asymptotic probability one, such a random subgroup H of G is a free group, and the semidirect product of H acting on E(G) is hyperbolically embedded in G, where E(G) is the unique maximal finite normal subgroup of G. △ Less

Submitted 1 January, 2017; originally announced January 2017.

The stratum of random mapping classes

Authors: Vaibhav Gadre, Joseph Maher

Abstract: We consider random walks on the mapping class group whose support generates a non-elementary subgroup and contains a pseudo-Anosov map whose invariant Teichmüller geodesic is in the principal stratum. For such random walks, we show that mapping classes along almost every infinite sample path are eventually pseudo-Anosov, with invariant Teichmüller geodesics in the principal stratum. This provides… ▽ More We consider random walks on the mapping class group whose support generates a non-elementary subgroup and contains a pseudo-Anosov map whose invariant Teichmüller geodesic is in the principal stratum. For such random walks, we show that mapping classes along almost every infinite sample path are eventually pseudo-Anosov, with invariant Teichmüller geodesics in the principal stratum. This provides an answer to a question of Kapovich and Pfaff. △ Less

Submitted 5 July, 2016; originally announced July 2016.

Comments: 12 pages, 2 figures

Morse area and Scharlemann-Thompson width for hyperbolic 3-manifolds

Authors: Diane Hoffoss, Joseph Maher

Abstract: Scharlemann and Thompson define a numerical complexity for a 3-manifold using handle decompositions of the manifold. We show that for compact hyperbolic 3-manifolds this is linearly related to a definition of metric complexity in terms of the areas of level sets of Morse functions. Scharlemann and Thompson define a numerical complexity for a 3-manifold using handle decompositions of the manifold. We show that for compact hyperbolic 3-manifolds this is linearly related to a definition of metric complexity in terms of the areas of level sets of Morse functions. △ Less

Submitted 31 March, 2015; v1 submitted 29 March, 2015; originally announced March 2015.

Comments: 19 pages, 1 figure. arXiv admin note: text overlap with arXiv:1411.2509 by other authors

Journal ref: Pacific J. Math. 281 (2016) 83-102

Random walks on weakly hyperbolic groups

Authors: Joseph Maher, Giulio Tiozzo

Abstract: Let G be a countable group which acts by isometries on a separable, but not necessarily proper, Gromov hyperbolic space X. We say the action of G is weakly hyperbolic if G contains two independent hyperbolic isometries. We show that a random walk on such G converges to the Gromov boundary almost surely. We apply the convergence result to show linear progress and linear growth of translation length… ▽ More Let G be a countable group which acts by isometries on a separable, but not necessarily proper, Gromov hyperbolic space X. We say the action of G is weakly hyperbolic if G contains two independent hyperbolic isometries. We show that a random walk on such G converges to the Gromov boundary almost surely. We apply the convergence result to show linear progress and linear growth of translation length, without any assumptions on the moments of the random walk. If the action is acylindrical, and the random walk has finite entropy and finite logarithmic moment, we show that the Gromov boundary with the hitting measure is the Poisson boundary. △ Less

Submitted 2 January, 2015; v1 submitted 15 October, 2014; originally announced October 2014.

Comments: 58 pages, 9 figures

MSC Class: 60G50; 20F67; 57M60

Random methods in 3-manifold theory

Authors: Alexander Lubotzky, Joseph Maher, Conan Wu

Abstract: We show that for any integers k and g, with g at least two, there are infinitely many closed hyperbolic 3-manifolds which are integral homology spheres with Casson invariant k, and Heegaard genus equal to g. This existence result is shown using random methods, using a model of random 3-manifolds arising from random walks on the mapping class group of a closed orientable surface. We show that for any integers k and g, with g at least two, there are infinitely many closed hyperbolic 3-manifolds which are integral homology spheres with Casson invariant k, and Heegaard genus equal to g. This existence result is shown using random methods, using a model of random 3-manifolds arising from random walks on the mapping class group of a closed orientable surface. △ Less

Submitted 25 May, 2014; originally announced May 2014.

Comments: 34 pages, 8 figures

Word length statistics for Teichmüller geodesics and singularity of harmonic measure

Authors: Vaibhav Gadre, Joseph Maher, Giulio Tiozzo

Abstract: Given a measure on the Thurston boundary of Teichmueller space, one can pick a geodesic ray joining some basepoint to a randomly chosen point on the boundary. Different choices of measures may yield typical geodesics with different geometric properties. In particular, we consider two families of measures: the ones which belong to the Lebesgue or visual measure class, and harmonic measures for rand… ▽ More Given a measure on the Thurston boundary of Teichmueller space, one can pick a geodesic ray joining some basepoint to a randomly chosen point on the boundary. Different choices of measures may yield typical geodesics with different geometric properties. In particular, we consider two families of measures: the ones which belong to the Lebesgue or visual measure class, and harmonic measures for random walks on the mapping class group generated by a distribution with finite first moment in the word metric. We consider the ratio between the word metric and the relative metric of approximating mapping class group elements along a geodesic ray, and prove that this ratio tends to infinity along almost all geodesics with respect to Lebesgue measure, while the limit is finite along almost all geodesics with respect to harmonic measure. As a corollary, we establish singularity of harmonic measure. We show the same result for cofinite volume Fuchsian groups with cusps. As an application, we answer a question of Deroin-Kleptsyn-Navas about the vanishing of the Lyapunov expansion exponent. △ Less

Submitted 20 October, 2014; v1 submitted 6 December, 2012; originally announced December 2012.

Comments: 53 pages, 9 figures. Extended main result to random walks with finite first moment in the word metric

MSC Class: 30F60; 37F30; 32G15; 20F65; 60J50

Exponential decay in the mapping class group

Authors: Joseph Maher

Abstract: We show that the probability that a finitely supported random walk on a non-elementary subgroup of the the mapping class group gives a non-pseudo-Anosov element decays exponentially in the length of the random walk. More generally, we show that if R is a set of mapping class group elements with an upper bound on their translation lengths on the complex of curves, then the probability that a random… ▽ More We show that the probability that a finitely supported random walk on a non-elementary subgroup of the the mapping class group gives a non-pseudo-Anosov element decays exponentially in the length of the random walk. More generally, we show that if R is a set of mapping class group elements with an upper bound on their translation lengths on the complex of curves, then the probability that a random walk lies in R decays exponentially in the length of the random walk. △ Less

Submitted 5 July, 2016; v1 submitted 28 April, 2011; originally announced April 2011.

Comments: 24 pages, 8 figures. v2: Fixed abstract. v3: Anna Lenzhen pointed out an error in the proof of Lemma 2.11, fixed in this version

Journal ref: J. London Math. Soc. (2012) 86(2), 366-386

Statistics and compression of scl

Authors: Danny Calegari, Joseph Maher

Abstract: We obtain sharp estimates on the growth rate of stable commutator length on random (geodesic) words, and on random walks, in hyperbolic groups and groups acting nondegenerately on hyperbolic spaces. In either case, we show that with high probability stable commutator length of an element of length $n$ is of order $n/\log{n}$. This establishes quantitative refinements of qualitative results of Be… ▽ More We obtain sharp estimates on the growth rate of stable commutator length on random (geodesic) words, and on random walks, in hyperbolic groups and groups acting nondegenerately on hyperbolic spaces. In either case, we show that with high probability stable commutator length of an element of length $n$ is of order $n/\log{n}$. This establishes quantitative refinements of qualitative results of Bestvina-Fujiwara and others on the infinite dimensionality of 2-dimensional bounded cohomology in groups acting suitably on hyperbolic spaces, in the sense that we can control the geometry of the unit balls in these normed vector spaces (or rather, in random subspaces of their normed duals). As a corollary of our methods, we show that an element obtained by random walk of length $n$ in a mapping class group cannot be written as a product of fewer than $O(n/\log{n})$ reducible elements, with probability going to 1 as $n$ goes to infinity. We also show that the translation length on the complex of free factors of a random walk of length $n$ on the outer automorphism group of a free group grows linearly in $n$. △ Less

Submitted 12 February, 2013; v1 submitted 29 August, 2010; originally announced August 2010.

Comments: Minor edits arising from referee's comments; 45 pages

Journal ref: Ergod. Th. Dynam. Sys. 35 (2015) 64-110

Flow-Based Propagators for the SEQUENCE and Related Global Constraints

Authors: Michael J. Maher, Nina Narodytska, Claude-Guy Quimper, Toby Walsh

Abstract: We propose new filtering algorithms for the SEQUENCE constraint and some extensions of the SEQUENCE constraint based on network flows. We enforce domain consistency on the SEQUENCE constraint in $O(n^2)$ time down a branch of the search tree. This improves upon the best existing domain consistency algorithm by a factor of $O(\log n)$. The flows used in these algorithms are derived from a linear… ▽ More We propose new filtering algorithms for the SEQUENCE constraint and some extensions of the SEQUENCE constraint based on network flows. We enforce domain consistency on the SEQUENCE constraint in $O(n^2)$ time down a branch of the search tree. This improves upon the best existing domain consistency algorithm by a factor of $O(\log n)$. The flows used in these algorithms are derived from a linear program. Some of them differ from the flows used to propagate global constraints like GCC since the domains of the variables are encoded as costs on the edges rather than capacities. Such flows are efficient for maintaining bounds consistency over large domains and may be useful for other global constraints. △ Less

Submitted 24 September, 2009; originally announced September 2009.

Comments: Principles and Practice of Constraint Programming, 14th International Conference, CP 2008, Sydney, Australia, September 14-18, 2008. Proceedings

ACM Class: I.2.4

Asymptotics for pseudo-Anosov elements in Teichmuller lattices

Authors: Joseph Maher

Abstract: A Teichmuller lattice is the orbit of a point in Teichmuller space under the action of the mapping class group. We show that the proportion of lattice points in a ball of radius r which are not pseudo-Anosov tends to zero as r tends to infinity. In fact, we show that if R is a subset of the mapping class group, whose elements have an upper bound on their translation length on the complex of curv… ▽ More A Teichmuller lattice is the orbit of a point in Teichmuller space under the action of the mapping class group. We show that the proportion of lattice points in a ball of radius r which are not pseudo-Anosov tends to zero as r tends to infinity. In fact, we show that if R is a subset of the mapping class group, whose elements have an upper bound on their translation length on the complex of curves, then proportion of lattice points in the ball of radius r which lie in R tends to zero as r tends to infinity. △ Less

Submitted 17 April, 2010; v1 submitted 17 January, 2009; originally announced January 2009.

Comments: 17 pages, 2 figures, revised version.

Random Heegaard splittings

Authors: Joseph Maher

Abstract: A random Heegaard splitting is a 3-manifold obtained by using a random walk of length n on the mapping class group as the gluing map between two handlebodies. We show that the joint distribution of random walks of length n and their inverses is asymptotically independent, and converges to the product of the harmonic and reflected harmonic measures defined by the random walk. We use this to show th… ▽ More A random Heegaard splitting is a 3-manifold obtained by using a random walk of length n on the mapping class group as the gluing map between two handlebodies. We show that the joint distribution of random walks of length n and their inverses is asymptotically independent, and converges to the product of the harmonic and reflected harmonic measures defined by the random walk. We use this to show that the translation length on the curve complex of a random walk grows linearly in the length of the walk, and similarly, that distance in the curve complex between the disc sets of a random Heegaard splitting grows linearly in n. In particular, this implies that a random Heegaard splitting is hyperbolic with asymptotic probability one. △ Less

Submitted 15 November, 2010; v1 submitted 28 September, 2008; originally announced September 2008.

Comments: 31 pages, 5 figures, revised version

MSC Class: 37E30; 20F65; 57M50

Linear progress in the complex of curves

Authors: Joseph Maher

Abstract: We show that a random walk on the mapping class group of an orientable surface of finite type makes linear progress in the relative metric, which is quasi-isometric to the complex of curves. We show that a random walk on the mapping class group of an orientable surface of finite type makes linear progress in the relative metric, which is quasi-isometric to the complex of curves. △ Less

Submitted 24 January, 2010; v1 submitted 4 February, 2008; originally announced February 2008.

Comments: 28 pages, 14 figures, final version

Random walks on the mapping class group

Authors: Joseph Maher

Abstract: We show that a random walk on the mapping class group of an orientable surface gives rise to a pseudo-Anosov element with asymptotic probability one. Our methods apply to many subgroups of the mapping class group, including the Torelli group. We show that a random walk on the mapping class group of an orientable surface gives rise to a pseudo-Anosov element with asymptotic probability one. Our methods apply to many subgroups of the mapping class group, including the Torelli group. △ Less

Submitted 17 November, 2010; v1 submitted 19 April, 2006; originally announced April 2006.

Comments: 31 pages, 7 figures. v2: Added references to work of Rivin and I. Kapovich. v3: This version now only contains the mapping class group results. The original application to 3-manifolds contained a gap, which is fixed in arXiv:0809.4881. v4: revised version

MSC Class: 37E30; 20F65; 57M50

Journal ref: Duke Math. J. 156, no. 3 (2011), 429-468

Embedding Defeasible Logic into Logic Programming

Authors: Grigoris Antoniou, David Billington, Guido Governatori, Michael J. Maher

Abstract: Defeasible reasoning is a simple but efficient approach to nonmonotonic reasoning that has recently attracted considerable interest and that has found various applications. Defeasible logic and its variants are an important family of defeasible reasoning methods. So far no relationship has been established between defeasible logic and mainstream nonmonotonic reasoning approaches. In this paper… ▽ More Defeasible reasoning is a simple but efficient approach to nonmonotonic reasoning that has recently attracted considerable interest and that has found various applications. Defeasible logic and its variants are an important family of defeasible reasoning methods. So far no relationship has been established between defeasible logic and mainstream nonmonotonic reasoning approaches. In this paper we establish close links to known semantics of logic programs. In particular, we give a translation of a defeasible theory D into a meta-program P(D). We show that under a condition of decisiveness, the defeasible consequences of D correspond exactly to the sceptical conclusions of P(D) under the stable model semantics. Without decisiveness, the result holds only in one direction (all defeasible consequences of D are included in all stable models of P(D)). If we wish a complete embedding for the general case, we need to use the Kunen semantics of P(D), instead. △ Less

Submitted 15 November, 2005; originally announced November 2005.

Comments: To appear in Theory and Practice of Logic Programming

ACM Class: F.4.1; I.2.3

Journal ref: Theory and Practice of Logic Programming, 6, 6 (2006): 703-735

Heegaard gradient and virtual fibers

Authors: Joseph Maher

Abstract: We show that if a closed hyperbolic 3-manifold has infinitely many finite covers of bounded Heegaard genus, then it is virtually fibered. This generalizes a theorem of Lackenby, removing restrictions needed about the regularity of the covers. Furthermore, we can replace the assumption that the covers have bounded Heegaard genus with the weaker hypotheses that the Heegaard splittings for the cove… ▽ More We show that if a closed hyperbolic 3-manifold has infinitely many finite covers of bounded Heegaard genus, then it is virtually fibered. This generalizes a theorem of Lackenby, removing restrictions needed about the regularity of the covers. Furthermore, we can replace the assumption that the covers have bounded Heegaard genus with the weaker hypotheses that the Heegaard splittings for the covers have Heegaard gradient zero, and also bounded width, in the sense of Scharlemann-Thompson thin position for Heegaard splittings. △ Less

Submitted 13 December, 2005; v1 submitted 10 November, 2004; originally announced November 2004.

Comments: Published by Geometry and Topology at http://www.maths.warwick.ac.uk/gt/GTVol9/paper51.abs.html

MSC Class: 57M10; 57M50

Journal ref: Geom. Topol. 9 (2005) 2227-2259

Propositional Defeasible Logic has Linear Complexity

Authors: Michael J. Maher

Abstract: Defeasible logic is a rule-based nonmonotonic logic, with both strict and defeasible rules, and a priority relation on rules. We show that inference in the propositional form of the logic can be performed in linear time. This contrasts markedly with most other propositional nonmonotonic logics, in which inference is intractable. Defeasible logic is a rule-based nonmonotonic logic, with both strict and defeasible rules, and a priority relation on rules. We show that inference in the propositional form of the logic can be performed in linear time. This contrasts markedly with most other propositional nonmonotonic logics, in which inference is intractable. △ Less

Submitted 24 May, 2004; originally announced May 2004.

Comments: Appeared in Theory and Practice of Logic Programming, vol. 1, no. 6, 2001

ACM Class: D.1.6; D.3.2

Journal ref: Theory and Practice of Logic Programming, vol. 1, no. 6, 2001

Period three actions on lens spaces

Authors: Joseph Maher

Abstract: We show that a free period three action on a lens space is standard, i.e. the quotient is homeomorphic to a lens space. This is an extension of the result for period three actions on the three-sphere, arXiv:math.GT/0204077, by the author and J. Hyam Rubinstein. We show that a free period three action on a lens space is standard, i.e. the quotient is homeomorphic to a lens space. This is an extension of the result for period three actions on the three-sphere, arXiv:math.GT/0204077, by the author and J. Hyam Rubinstein. △ Less

Submitted 3 February, 2008; v1 submitted 2 November, 2003; originally announced November 2003.

Comments: 67 pages, 54 pictures

MSC Class: 57M60

Journal ref: Algebr. Geom. Topol. 7 (2007) 2021-2102

A Model-Theoretic Semantics for Defeasible Logic

Authors: Michael J. Maher

Abstract: Defeasible logic is an efficient logic for defeasible reasoning. It is defined through a proof theory and, until now, has had no model theory. In this paper a model-theoretic semantics is given for defeasible logic. The logic is sound and complete with respect to the semantics. We also briefly outline how this approach extends to a wide range of defeasible logics. Defeasible logic is an efficient logic for defeasible reasoning. It is defined through a proof theory and, until now, has had no model theory. In this paper a model-theoretic semantics is given for defeasible logic. The logic is sound and complete with respect to the semantics. We also briefly outline how this approach extends to a wide range of defeasible logics. △ Less

Submitted 25 July, 2002; originally announced July 2002.

Comments: 14 pages. Originally published in proc. PCL 2002, a FLoC workshop; eds. Hendrik Decker, Dina Goldin, Jorgen Villadsen, Toshiharu Waragai (http://floc02.diku.dk/PCL/)

ACM Class: F.4.1; I.2.3; I.2.4

Period three actions on the three-sphere

Authors: Joseph Maher, J. Hyam Rubinstein

Abstract: We show that a free period three action on the three-sphere is standard, i.e. the quotient is homeomorphic to a lens space. We use a minimax argument involving sweepouts. We show that a free period three action on the three-sphere is standard, i.e. the quotient is homeomorphic to a lens space. We use a minimax argument involving sweepouts. △ Less

Submitted 10 July, 2003; v1 submitted 6 April, 2002; originally announced April 2002.

Comments: Published by Geometry and Topology at http://www.maths.warwick.ac.uk/gt/GTVol7/paper11.abs.html

Report number: UCSB Math 2002-5 MSC Class: 57M60; 57M50

Journal ref: Geom. Topol. 7 (2003) 329-397

Representation results for defeasible logic

Authors: G. Antoniou, D. Billington, G. Governatori, M. J. Maher

Abstract: The importance of transformations and normal forms in logic programming, and generally in computer science, is well documented. This paper investigates transformations and normal forms in the context of Defeasible Logic, a simple but efficient formalism for nonmonotonic reasoning based on rules and priorities. The transformations described in this paper have two main benefits: on one hand they c… ▽ More The importance of transformations and normal forms in logic programming, and generally in computer science, is well documented. This paper investigates transformations and normal forms in the context of Defeasible Logic, a simple but efficient formalism for nonmonotonic reasoning based on rules and priorities. The transformations described in this paper have two main benefits: on one hand they can be used as a theoretical tool that leads to a deeper understanding of the formalism, and on the other hand they have been used in the development of an efficient implementation of defeasible logic. △ Less

Submitted 29 March, 2000; originally announced March 2000.

Comments: 30 pages, 1 figure

ACM Class: F.4.1; I.2.3; I.2.4

Journal ref: ACM Transactions on Computational Logic, 2 (2), 255--287, 2001

A flexible framework for defeasible logics

Authors: G. Antoniou, D. Billigton, G. Governatori, M. J. Maher

Abstract: Logics for knowledge representation suffer from over-specialization: while each logic may provide an ideal representation formalism for some problems, it is less than optimal for others. A solution to this problem is to choose from several logics and, when necessary, combine the representations. In general, such an approach results in a very difficult problem of combination. However, if we can c… ▽ More Logics for knowledge representation suffer from over-specialization: while each logic may provide an ideal representation formalism for some problems, it is less than optimal for others. A solution to this problem is to choose from several logics and, when necessary, combine the representations. In general, such an approach results in a very difficult problem of combination. However, if we can choose the logics from a uniform framework then the problem of combining them is greatly simplified. In this paper, we develop such a framework for defeasible logics. It supports all defeasible logics that satisfy a strong negation principle. We use logic meta-programs as the basis for the framework. △ Less

Submitted 6 March, 2000; originally announced March 2000.

Comments: Proceedings of 8th International Workshop on Non-Monotonic Reasoning, April 9-11, 2000, Breckenridge, Colorado

ACM Class: I.2.3; D.1.6

Virtually embedded boundary slopes

Authors: Joseph Maher

Abstract: We show that for certain hyperbolic 3-manifolds, all boundary slopes are slopes of immersed incompressible surfaces, covered by incompressible embeddings in some finite cover. The manifolds include hyperbolic punctured torus bundles and hyperbolic two-bridge knots. We show that for certain hyperbolic 3-manifolds, all boundary slopes are slopes of immersed incompressible surfaces, covered by incompressible embeddings in some finite cover. The manifolds include hyperbolic punctured torus bundles and hyperbolic two-bridge knots. △ Less

Submitted 9 January, 1999; originally announced January 1999.

Comments: 10 pages, 3 figures, Latex2e

Report number: UCSB Math 1999-1 MSC Class: 57M10; 57M25