Chapter 8 Algebraic Methods for Optimization Problems (2009)
Richard Bird, Jeremy Gibbons, Shin-cheng Mu
Abstract. We argue for the benefits of relations over functions for modelling programs, and even more so for modelling specifications. To support this argument, we present an extended case study for...
FUNCTIONAL PEARL Inverting the Burrows-Wheeler Transform Abstract (2008)
The objective of this pearl is to derive the inverse of the Burrows-Wheeler transform from its specification, using simple equational reasoning. In fact, we derive the inverse of a more general...
Richard Bird, Lambert Meertens
Abstract. A nested datatype, also known as a non-regular datatype, is a parametrised datatype whose declaration involves different instances of the accompanying type parameters. Nested datatypes have...
Program Optimisation, Naturally (2007)
Richard Bird, Jeremy Gibbons, Geraint Jones
this paper we derive another, quite di#erent, linear-time algorithm for reversing a list. The derivation relies on a higherorder naturality [5] property of the function unzip, the function that turns...
A nexus is a tree that contains shared nodes, nodes that have more than one incoming arc. Shared nodes are created in almost every functional program—for instance, when updating a purely functional...
The Burrows-Wheeler Transform is a string-to-string transform which, when used as a preprocessing phase in compression, significantly enhances the compression rate. However, it often puzzles people...
Theory and Applications of Inverting Functions as Folds (2007)
This paper is devoted to the proof, applications, and generalisation of a theorem, due to Bird and de Moor, that gave conditions under which a total function can be expressed as a relational fold....
Theory and Applications of Inverting Functions as Folds (2007)
This paper is devoted to the proof and applications of a theorem giving conditions under which the inverse of a partial function can be expressed as a relational hylomorphism. The theorem is a...
Our aim in this pearl is to exploit simple equational reasoning to derive the inverse of the Burrows-Wheeler transform from its specication. As a bonus, we will also sketch the outlines of deriving...
Enumerating the Rationals (2007)
We present a series of lazy functional programs for enumerating the rational numbers without duplication, drawing on some elegant results of Neil Calkin, Herbert Wilf and Moshe Newman. 1
Passenger casualties in non-collision incidents on buses and coaches in Great Britain (2003)
Kirk, Alan, Grant, Rachel, Bird, Richard
This is a conference paper.
Passenger casualties in non-collision incidents on buses and coaches in Great Britain (2003)
Kirk, Alan, Grant, Rachel, Bird, Richard
This is a conference paper.
Arithmetic coding with folds and unfolds (2003)
Arithmetic coding is a method for data compression. Although the idea was
Why do passengers get hurt when buses don't crash? (2002)
Grant, Rachel, Kirk, Alan, Bird, Richard
This is a conference paper.
Why do passengers get hurt when buses don't crash? (2002)
Grant, Rachel, Kirk, Alan, Bird, Richard
This is a conference paper.
Inverting functions as folds (2002)
Abstract. This paper describes a technique for constructing the inverse of a partial function as a relational hylomorphism. When the function is total, the inverse is expressed as a relational fold....
Functional Quantum Programming (2001)
It has been shown that non-determinism, both angelic and demonic, can be encoded in a functional language in di#erent representation of sets. In this paper we see quantum programming as a special...
Lane, F. J., Bird, Richard, Flynn, Brian M., Cooley, W. A., Mensch, Samuel R.
The Chief Financial Officers Act of 1990, as amended by the Federal Financial Management Act of 1994, requires the Inspector General, DoD, or an appointee to audit the DoD financial statements. We...
Assessment of passenger safety in local service psv's: final report. (1999)
Bird, Richard, Quigley, Claire
Department for Transport
Assessment of passenger safety in local service psv's: final report. (1999)
Bird, Richard, Quigley, Claire
Department for Transport
Generalised Folds for Nested Datatypes (1999)
Nested datatypes generalise regular datatypes in much the same way that context-free languages generalise regular ones. Although the categorical semantics of nested types turns out to be similar to...
Generic Programming With Relations and Functors (1999)
Richard Bird, Oege De Moor, Paul Hoogendijk
This paper explores the idea of generic programming in which programs are parameterised by data types. Part of the constructive theory of lists, specically the part dealing with properties of...
Program Optimisation, Naturally (1999)
Richard Bird, Jeremy Gibbons, Geraint Jones
It is well-known that each polymorphic function satises a certain equational law, called a naturality condition. Such laws are part and parcel of the basic toolkit for improving the eÆciency of...
Il giardino con le rampicanti (1999)
Il giardino con le rampicanti, Richard Bird, fotografie di Stephen Robson. . - Novara. NALUAF000540, De Agostini. NAEDAF001084, 1999.
Creare siepi e bordure, Richard Bird, fotografie di Stephen Robson. . - Novara. NALUAF000540, De Agostini. NAEDAF001084, 1999.
Granetto, Paul J., Bird, Richard, Kornides, James L., Frontz, Amy J., Currier, Kevin C.
We performed this audit in response to the Chief Financial Officers Act of 1990, as amended by the Federal Financial Management Act of 1994. Inventory and inventory-related transactions represent...
Financial Management: DoD Payroll Withholding Data for FY 2002 (1998)
Granetto, Paul J., Bird, Richard, Vincent, David F., Winter, Thomas J., Powell, Joseph A.
This report is intended for use by the Inspector General, the Chief Financial Officer, and the Associate Director for Retirement and Insurance at the Office of Personnel Management. The report...
Décentralisation financière et pays en dévelopement: concepts, mesure et évaluation (1997)
BIRD, Richard, VAILLANCOURT, François
Ce texte présente ce qu’est la décentralisation fiscale, fait ressortir ses forces et ses faiblesses et identifie les raisons de son succès, le tout dans le contexte de huit pays en...
From Dynamic Programming to Greedy Algorithms (1992)
A calculus of relations is used to reason about specifications and algorithms for optimisation problems. It is shown how certain greedy algorithms can be seen as refinements of dynamic programming....
Solving Optimisation Problems with Catamorphisms (1992)
. This paper contributes to an ongoing effort to construct a calculus for deriving programs for optimisation problems. The calculus is built around the notion of initial data types and catamorphisms...
Expenditure-Based Equalization Transfers
Francois Vaillancourt, Richard Bird
This paper is divided into three main sections. In the first section, we set out briefly the standard theoretical case for both a general equalization transfer and for the incorporation of...
Bird, Richard, Wallich, Christine
The decentralization of government in Eastern Europe represents a reaction both from below (to tight central political control) and from above (to privatize the economy and relieve the central...
China's Fiscal System: A Work in Progress
We argue in this paper that unless China begins to tackle more systematically the serious problems that have emerged in the finances of its various levels of sub-national government the problems to...
Is VAT the Best Way to Impose a General Consumption Tax in Developing Countries
Richard Bird, Pierre-Pascal Gendron
In this paper we discuss some recent critical literature on VAT in developing countries relating to its revenue productivity, its equity, and its impact on the development of the formal economy....
Tax Effort: The Impact of Corruption, Voice and Accountability
Richard Bird, Jorge Martinez-Vazquez, Benno Torgler
In this paper we argue that a more legitimate and responsive state is an essential factor for a more adequate level of tax effort in developing countries. While at first glance giving such advice to...
Tax Effort: The Impact of corruption, Voice and Accountability
Richard Bird, Jorge Martinez-Vazquezb, Benno Torgler
In this paper we argue that a more legitimate and responsive state is an essential factor for a more adequate level of tax effort in developing countries. while at first glance giving such advice to...
Reforming Ontario’s Property Tax System: A Never-Ending Story?
Enid Slack, Almos Tassonyi, Richard Bird
This paper reviews the development of property tax policy in the province of Ontario, Canada, over the last two centuries. This review underlines the highly political nature of property tax policy at...
Tax Policy in Emerging Countries
We consider in this paper how emerging countries may in practice best design and develop tax policies, given the complex economic and political environments they face. After an overview of what tax...
Decentralizing infrastructure : for good or ill?
The author examines the many faces of infrastructure decentralization: the costs and benefits, the government structure (constraint or variable?), the"polycentric"approach, and how to make...
Financing local government in Hungary
Bird, Richard, Wallich, Christine
Hungary has undertaken a bold and far-ranging reform of its system of subnational finances. This paper outlines the changes introduced in the system of local finance as a result of the 1990 Local...
Closing the Gap: Fiscal Imbalaces and Intergovernmental Transfers in Developed Federations
This paper discusses the concepts of vertical fiscal imbalance (the fiscal gap) and horizontal fiscal imbalance (equalization) and uses several statistics to measure these concepts for eight...
Earmarking in Theory and Korean Practice
In the first part of this paper we present a non-technical analysis of earmarking. We then briefly review some international experience with earmarking and its apparent results. The main new...
Décentralisation financière et pays en dévelopement: concepts, mesure et évaluation
BIRD, Richard, VAILLANCOURT, François
Ce texte présente ce qu’est la décentralisation fiscale, fait ressortir ses forces et ses faiblesses et identifie les raisons de son succès, le tout dans le contexte de huit pays en...
Dual VATs and Cross-Border Trade: Two Problems, One Solution?
In recent years, two distinct but related questions have been raised with respect to value-added taxes (VATs). Concern has been expressed over whether it is desirable or even possible for both...
CVAT, VIVAT, and Dual VAT: Vertical ``Sharing'' and Interstate Trade
Richard Bird, Pierre-Pascal Gendron
We compare and contrast theCVAT and VIVAT approaches discussed in the preceding papers byMcLure and Keen and Smith with the dual VAT originally discussedin our 1998 paper. We conclude that each of...
Fiscal Federalism in Russia: A Canadian Perspective
This paper considers some of the key instrumental components of intergovernmental fiscal relations that arise in the Russian Federation -- expenditures, revenues, transfers, borrowing, and...
Tax Policy and Tax Research in Canada
Richard Bird, Michael Smart, Patrick Grady, Andrew Sharpe
In a survey of tax reform in recent years, Richard Bird and Michael Smart explore the relationship between tax policy and tax research. They conclude that there have been important examples of...
Tax Challenges Facing Developing Countries
Taxes matter. We all know we need them to pay for public services. But most of us complain about them -- exercise our "voice" -- and often try to dodge them -- to "exit" -- when we can. Those who...
The VAT in Developing and Transitional Countries
Bird,Richard, Gendron,Pierre-Pascal
Value-added tax (VAT) now dominates tax systems around the world. But should every country have a VAT? Is the current VAT always as good as it could be in economic, equity, and administrative terms?...