Monotonic sequence games (2009)
M. H. Albert, M. D. Atkinson, C. C. Handley, D. A. Holton, D. J. Mccaughan, ...
Abstract. In a monotonic sequence game, two players alternately choose elements of a sequence from some fixed ordered set. The game ends when the resulting sequence contains either an ascending...
Permutation classes of polynomial growth (2008)
M. H. Albert, M. D. Atkinson, Robert Brignall
A pattern class is a set of permutations closed under the formation of subpermutations. Such classes can be characterised as those permutations not involving a particular set of forbidden...
1 The combinatorics of some abstract data types (2008)
Abstract data types (ADTs) may be regarded as abstract machines and then a program for an ADT is any sequence of operations allowed by its specification. The effect of such programs on container ADTs...
A NEW PROOF OF A THEOREM OF SOLOMON (2008)
The main purpose of this note is to give another proof and a different view of a theorem of Solomon [3] on Coxeter groups (finite groups of symmetries of R n generated by reflections). A secondary...
A simple permutation is one that does not map any non-trivial interval onto an interval. It is shown that, if the number of simple permutations in a pattern restricted class of permutations is...
The Complexity of Algorithms (2008)
The modern theory of algorithms dates from the late 1960s when the method of asymptotic execution time measurement began to be used. It is argued that the subject has both an engineering and...
Abstract Restricted Permutations (2008)
Restricted permutations are those constrained by having to avoid subsequences ordered in various prescribed ways. They have functioned as a convenient descriptor for several sets of permutations...
Editor Generalized Priority Queues (2008)
Ian Munro, M. D. Atkinson, N. Santoro, T. Strothotte
ABSTRACT:,4 simple implementation of double-ended priority queues is presented. The proposed structure, called a min-max heap, can be built in linear time; in contrast to conventional heaps, it...
Some equinumerous pattern-avoiding classes of permutations (2008)
contain no pattern of the form αβγ where |α | = r, |γ | = s and β is any arrangement of {1, 2,..., p}∪{m−q+1, m− q + 2,..., m} is considered. A recurrence relation to enumerate the...
Monotonic sequence games (2008)
M. H. Albert, M. H. Albert, M. D. Atkinson, M. D. Atkinson, ...
Abstract. In a monotonic sequence game, two players alternately choose elements of a sequence from some fixed ordered set. The game ends when the resulting sequence contains either an ascending...
Regular closed sets of permutations (2008)
Machines whose main purpose is to permute and sort data are studied. The sets of permutations that can arise are analysed by means of finite automata and avoided pattern techniques. Conditions are...
Mike Atkinson, Michael Albert, M. H. Albert, M. D. Atkinson
Simple permutations and pattern restricted permutations Authors:
The p-modular Descent Algebra of the Symmetric Group (2007)
The descent algebra of the symmetric group, over a field of non-zero characteristic p, is studied. A homomorphism into the algebra of generalised p-modular characters of the symmetric group is...
Department of Computer Science, (2007)
N. Ruskuc, M. D. Atkinson, M. D. Atkinson, M. M. Murphy, M. M. Murphy, N. Rukuc
Partially well-ordered closed sets of permutations Authors:
M. H. Albert, M. D. Atkinson, M. D. Atkinson, D. A. Holton, ...
Algorithms for pattern involvement in permutations
Status: Submitted to Electronic.1ournal of Combinatorics (2007)
C. C. Handley, D. A. Holton, W. Stromquist, M. H. Albert, M. H. Albert, ...
On packing densities of permutations Authors:
Safe communication for card players by combinatorial designs for two-step protocols
On packing densities of permutations (2007)
M. H. Albert, M. D. Atkinson, C. C. Handley, D. A. Holton, W. Stromquist
The density of a permutation pattern π in a permutation σ is the proportion of subsequences of σ of length |π | that are isomorphic to π. The maximal value of the density is found for several...
The $p$-modular descent algebras (2007)
Atkinson, M. D., Pfeiffer, G., Van Willigenburg, S. J.
The concept of descent algebras over a field of characteristic zero is extended to define descent algebras over a field of prime characteristic. Some basic algebraic structure of the latter,...
The p-modular Descent Algebra of the Symmetric Group (2007)
Atkinson, M. D., Van Willigenburg, S. J.
The descent algebra of the symmetric group, over a field of non-zero characteristic p, is studied. A homomorphism into the algebra of generalised p-modular characters of the symmetric group is...
Avoiding bias in cards cryptography (2007)
Atkinson, M. D., Van Ditmarsch, H. P., Roehling, S.
We outline the need for stricter requirements for unconditionally secure cryptographic protocols inspired by the Russian Cards problem. A new requirement CA4 is proposed that checks for bias in...
Permutation classes of polynomial growth (2007)
R. Brignall, M. H. Albert, M. H. Albert, M. D. Atkinson, M. D. Atkinson, Robert Brignall
A pattern class is a set of permutations closed under the formation of subpermutations. Such classes can be characterized as those permutations not involving a particular set of forbidden...
Solomon's Descent Algebra Revisited (2006)
Starting from a non-standard definition, the descent algebra of the symmetric group is investigated. Homomorphisms into the tensor product of smaller descent algebras are defined. They are used to...
Permutation Classes of Polynomial Growth (2006)
Albert, M. H., Atkinson, M. D., Brignall, Robert
A pattern class is a set of permutations closed under the formation of subpermutations. Such classes can be characterised as those permutations not involving a particular set of forbidden...
M. H. Albert, M. D. Atkinson, C. C. Handley, D. A. Holton, ...
Weak and strong sorting classes are pattern-closed classes that are also closed downwards under the weak and strong orders on permutations.
Some equinumerous pattern-avoiding classes of permutations (2005)
Suppose that p,q,r,s are non-negative integers with m=p+q+r+s. The class X(p,q,r,s) of permutations that contain no pattern of the form αβγ where |α|=r, |γ|=s and β is any arrangement of...
Pattern avoidance classes and subpermutations (2004)
Atkinson, M. D., Murphy, M. M., Ruskuc, N.
Pattern avoidance classes of permutations that cannot be expressed as unions of proper subclasses can be described as the set of subpermutations of a single bijection. In the case that this bijection...
Restricted permutations and queue jumping (2004)
M. H. Albert, M. D. Atkinson, H. Van, D. A. Holton, ...
A connection between permutations that avoid 4231 and a certain queueing discipline is established. It is proved that a more restrictive queueing discipline corresponds to avoiding both 4231 and...
Compositions of pattern restricted sets of permutations (2004)
M. H. Albert, M. D. Atkinson, D. A. Holton, ...
The composition of two pattern restricted classes X,Y is the set of all permutation products ## where # X,# Y . This set is also defined by pattern restrictions. Examples are given where this set of...
The enumeration of simple permutations (2003)
Albert, M. H., Atkinson, M. D., Klazar, M.
A simple permutation is one which maps no proper non-singleton interval onto an interval. We consider the enumeration of simple permutations from several aspects. Our results include a...
The enumeration of simple permutations (2003)
M. H. Albert, M. D. Atkinson, M. Klazar
The enumeration of simple permutations
The enumeration of simple permutations (2003)
M. H. Albert, M. D. Atkinson, M. Klazar
A simple permutation is one which maps no proper non-singleton interval onto an interval. We consider the enumeration of simple permutations from several aspects. Our results include a...
Sorting with a Forklift (2003)
A fork stack is a generalised stack which allows pushes and pops of several items at a time. We consider the problem of determining which input streams can be sorted using a single forkstack, or...
Sorting with a Forklift (2003)
A fork stack is a generalised stack which allows pushes and pops of several items at a time. We consider the problem of determining which input streams can be sorted using a single forkstack, or...
The enumeration of simple permutations (2003)
M. H. Albert, M. D. Atkinson, M. Klazar
A simple permutation is one which maps no proper non-singleton interval onto an interval. We consider the enumeration of simple permutations from several aspects. Our results include a...
Partially well-ordered closed sets of permutations (2003)
It is known that the “pattern containment ” order on permutations is not a partial well-order. Nevertheless, many naturally defined subsets of permutations are partially well-ordered, in which...
Restricted permutations and queue jumping (2002)
Albert, M. H., Aldred, R. E. L., Atkinson, M. D., Van Ditmarsch, H., Handley, C. C., Holton, D. A.
A connection between permutations that avoid 4231 and a certain queueing discipline is established. It is proved that a more restrictive queueing discipline corresponds to avoiding both 4231 and...
Sorting with a forklift (2002)
Albert, M. H., Atkinson, M. D.
A fork stack is a generalised stack which allows pushes and pops of several items at a time. We consider the problem of determining which input streams can be sorted using a single forkstack, or...
Regular closed classes of permutations (2002)
Albert, M., Atkinson, M. D., Ruskuc, N.
Machines whose main purpose is to permute and sort data are studied. The sets of permutations that can arise are analysed by means of finite automata and avoided pattern techniques. Conditions are...
Sorting with a forklift (2002)
M. H. Albert, M. H. Albert, M. D. Atkinson, M. D. Atkinson
A fork stack is a generalised stack which allows pushes and pops of several items at a time. We consider the problem of determining which input streams can be sorted using a single forkstack, or...
Sorting With Two Ordered Stacks in Series (2002)
Atkinson Murphy Ru, M. D. Atkinson, M. M. Murphy
The permutations that can be sorted by two stacks in series are considered, subject to the condition that each stack remains ordered. A forbidden characterisation of such permutations is obtained and...
On Packing Densities of Permutations (2002)
M. H. Albert, M. D. Atkinson, C. C. Handley, D. A. Holton, W. Stromquist
The density of a permutation pattern in a permutation is the proportion of subsequences of of length jj that are isomorphic to . The maximal value of the density is found for several patterns , and...
Sorting with a forklift (2002)
Abstract. A fork stack is a stack that allows pushes and pops of several items at a time. An algorithm to determine which sequences of input streams can be sorted by a fork stack is given. The...
Algorithms for pattern involvement in permutations (2001)
M. H. Albert, M. D. Atkinson, D. A. Holton
We consider the problem of developing algorithms for the recognition of a fixed pattern within a permutation. These methods are based upon using a carefully chosen chain or tree of subpatterns to...
Permutation Involvement and Groups (2001)
Atkinson, M. D., Beals, Robert
Sets of permutations which are closed under both pattern involvement and multiplication are classified.
Permutations Which Are the Union of an Increasing and a Decreasing Subsequence (1998)
It is shown that there are # 2n n # - # n-1 m=0 2 n-m-1 # 2m m # permutations which are the union of an increasing sequence and a decreasing sequence. 1991 Mathematics Subject Classification 05A15...
Permutations Which Are the Union of an Increasing and a Decreasing Subsequence (1998)
Atkinson School, M. D. Atkinson
It is shown that there are \Gamma 2n n \Delta \Gamma P n\Gamma1 m=0 2 n\Gammam\Gamma1 \Gamma 2m m \Delta permutations which are the union of an increasing sequence and a decreasing sequence. 1991...
Priority Queues and Multisets (1995)
M. D. Atkinson, S. A. Linton, L.A. Walker, North Haugh
A priority queue, a container data structure equipped with the operations insert and delete-minimum, can re-order its input in various ways, depending both on the input and on the sequence of...
Priority queues and multisets (1995)
A priority queue, a container data structure equipped with the operations insert and delete-minimum, can re-order its input in various ways, depending both on the input and on the sequence of...
Computer Science Permutations generated by token passing in graphs (1995)
M. D. Atkinson, M. J. Livesey, D. Tulley
Communicated by MS. Paterson A transportation graph is a directed graph with a designated input node and a designated output node. Initially, the input node contains an ordered set of tokens 1,2,3,.....
Priority Queues and Multi-sets (1994)
M. D. Atkinson, S. A. Linton, L.A. Walker
data types are a fundamental design tool in modern software systems. Although there is an infinity of possible data types there is a small number only of them which recur frequently in algorithm...
Uniform Generation of Rooted Ordered Trees with Prescribed Degrees (1993)
An efficient algorithm is given for generating uniformly at random a rooted tree with a specified number of nodes of each degree. The algorithm requires linear time, needs hardly any auxiliary...
0 1988 by Kluwer Academic Publishers On the Width of an Orientation of a Tree* (1987)
Abstract. There are 2”-t ways in which a tree on n vertices can be oriented. Each of these can be regarded as the (Hasse) diagram of a partially ordered set. The maximal and minimal widths of these...