Ian N Roberts
email: ian.roberts@bbsrc.ac.uk

Stephen G Oliver

The Yin and Yang of Yeast: Biodiversity Research and Systems Biology as Complementary Forces Driving Innovation in Biotechnology

Introduction

The aim of this article is to review how yeast has contributed to contemporary biotechnology and to seek underlying principles relevant to its future exploitation for human benefit. Recent advances in systems biology combined with new knowledge of genome diversity promise to make yeast the eukaryotic workhorse of choice for production of everything from probiotics and pharmaceuticals to fuels and chemicals. The ability to engineer new capabilities through introduction of controlled diversity based on a complete understanding of genome complexity and metabolic flux is key. Here, we briefly summarise the history that has led to these apparently simple organisms being employed in such a broad range of commercial applications. Subsequently, we discuss the likely consequences of current yeast research for the future of biotechnological innovation.

Yeast at the forefront of biotechnology

•

Mankind"s earliest biotechnology

The ancient Egyptians are usually credited with the first proven use of yeast, largely as a result of the discovery of 4,000 year old hieroglyphics depicting clearly recognisable brewing and baking procedures. However, it is likely that mankind"s earliest use pre-dates even the origins of agriculture. Virtually all human societies are believed to have utilised yeasts in some way or other for a variety of food and beverage fermentations. Nevertheless, it was not until the work of Louis Pasteur and others in the 1800s that the true living nature of these predominantly single-celled fungi was unambiguously defined [START_REF] Barnett | A history of research on yeasts 2: Louis Pasteur and his contemporaries[END_REF]. Subsequent rapid progress in microbiology (including the development of the first vaccines) and in biochemistry (the word "enzyme" itself is derived from the Greek words meaning "in yeast") led to the emergence of yeast as a leading model organism in biological research [START_REF] Barnett | Beginnings of microbiology and biochemistry: the contribution of yeast research[END_REF]).

• First pure cultures and strain collections

The development of sterile technique and the adoption of pure yeast cultures in commercial brewing during the early 1900s was perhaps the most important innovation as regards the use of yeast in modern biotechnology. Recognition of variation in the growth and fermentation characteristics of different pure cultures provided the opportunity to launch targeted strain improvement programmes. The first collections of yeasts with defined characteristics were assembled by Hansen around the turn of the twentieth century [START_REF] Barnett | A history of research on yeasts 3: Emil Fischer, Eduard Buchner and their contemporaries[END_REF]. Public domain culture collections effectively came into being with the publication of the first catalogue of microbial strains by Král in 1900 [START_REF] Uruburu | History and services of culture collections International[END_REF] Today, tens of thousands of different strains are available from culture collections worldwide.

For example, the first page of a Google search for "yeast culture collection" in August 2010 yielded direct links to the National Collection of Yeast Cultures (UK), the Phaff Yeast Culture Collection (USA), the American Type Culture Collection (USA), the VTT culture collection (Finland) and the World Data Centre for Microorganisms (Japan). The last site links to 568 public domain culture collections in 68 countries, most notably the CBS (Netherlands) which maintains Hansen"s original yeast collections alongside taxonomic type strains of more than 1,000 other yeast species described to date.

The holdings of the public domain culture collections are only the tip of the iceberg. Thousands more proprietary strains are held by private organisations in the commercial biotechnology sector. Nevertheless, these public collections are significant: they provide back-up resources to safeguard commercially important genetic variation against market failures; they offer state-of-the-art identification facilities to meet an ever-increasing demand for precision characterisation of yeast strains of biotechnological interest; and they are invaluable in the academic sphere as a source of expertise and fully-authenticated material for biological research (Boundy-Mills 2010). In short, they provide the capability for the biotechnological advances described below and, most importantly of all, guarantee the reproducibility of the scientific experimentation on which these advances are based.

• Pioneering genetic transformation work

Despite considerable progress in yeast genetics during the early 1900s to 1960s, the next most important biotechnological innovation could be considered to be the achievement of genetic transformation in the 1970s [START_REF] Beggs | Transformation of yeast by a replicating hybrid plasmid[END_REF][START_REF] Hinnen | Transformation of yeast Proc[END_REF]. Although the use of genetically manipulated organisms in food biotechnology remains politically sensitive in some parts of the world, the use of patented genetically modified yeast to meet contemporary societal demands, such as producing pharmaceuticals and carbon neutral "second generation" biofuels, appears to have achieved widespread acceptance. Furthermore, the application of "reverse genetics" techniques from the 1980s onwards has rapidly accelerated fundamental understanding of basic yeast biology. The armoury of tools and resources available to the present day yeast researcher or biotechnologist is unrivalled by any other eukaryotic organism.

• First eukaryotic "omics and establishment of large-scale databases

The small size of the Saccharomyces cerevisiae yeast genome relative to other eukaryotes, coupled with a century-long history as a model organism in genetics (alongside its considerable commercial and medical importance), led to its selection for the first eukaryotic whole genome sequencing project. This EU-funded project began in the early 1990s and effectively laid the scientific foundations for the human genome project and many other subsequent large-scale sequencing projects. The completion of the EU Saccharomyces cerevisiae genome project [START_REF] Goffeau | Life with 6000 genes[END_REF] and its comprehensive bioinformatics analysis [START_REF] Mewes | Overview of the yeast genome[END_REF] created a need for a genome database for this yeast. There are two comprehensive S. cerevisiae yeast genome databases -SGD [START_REF] Engel | Saccharomyces Genome Database provides mutant phenotype data[END_REF] and CYGD [START_REF] Mewes | MIPS: analysis and annotation of genome information in[END_REF]. They take complementary approaches to the annotation of gene function and can usefully be employed in conjunction. No other biotechnologically important yeast has a comparable database, but Table 1 provides links to genome databases for other yeast species as well as to more specialised databases that relate exclusively to S. cerevisiae.

The EU yeast genome project was followed by the construction of sets of gene deletion mutants for each of the approximately 6,000 genes discovered [START_REF] Scherens | The uses of genome-wide yeast mutant collections[END_REF] and a new era of functional genomics. Since then sequencing costs have fallen dramatically. Genome re-sequencing projects (e.g. [START_REF] Wei | Genome sequencing and comparative analysis of Saccharomyces cerevisiae strain YJM789[END_REF][START_REF] Doniger | A catalog of neutral and deleterious polymorphism in yeast[END_REF], Bornemann et al 2008[START_REF] Dimitrov | Polymorphisms in multiple genes contribute to the spontaneous mitochondrial genome instability of Saccharomyces cerevisiae S288C strains[END_REF][START_REF] Liti | Population genomics of domestic and wild yeasts[END_REF][START_REF] Schacherer | Comprehensive polymorphism survey elucidates population structure of Saccharomyces cerevisiae[END_REF][START_REF] Dowell | Genotype to phenotype: a complex problem[END_REF], new robotic techniques and the construction of mathematical and logical models (e.g. [START_REF] King | The automation of science[END_REF] have led to the generation of a rapidly increasing number of sequence databanks, genetic resources and computational tools, to the point that the yeast-associated scientific infrastructure, including culture collections and data centres, has expanded beyond recognition. The NCBI Entrez Genome Project database now lists 19 separate genome sequencing projects for Saccharomyces cerevisiae alone. Entries include several commercially important wine strains in addition to the laboratory and environmental isolates that were the focus of the earlier studies. Vast volumes of new information relevant to future biotechnological innovation continue to be produced. Two examples are given below.

• Leading computational models of cell function

The history of biotechnological innovation shows a clear dependence upon advances in understanding of fundamental biology. Early exploitation of strain variation depended upon isolation of pure cultures and recognition of their biological nature. Later innovations depended upon modification of biochemical pathways based on scientifically-established genetic principles. The next major advances will probably derive from the latest "systems" level understanding of cellular organisation emerging from computational genomics. This is one motivation behind current research to develop mathematical models of the entire biochemical repertoire of a single cell. The latest models of gene expression, biochemical pathways and metabolic flux through cellular networks are leading to the ability to apply engineering design principles to achieve high level control, thus expediting strain improvement. Yeast is again leading the way with the most accurate computational model of a eukaryotic cell metabolism achieved to date [START_REF] Herrgård | A consensus yeast metabolic network reconstruction obtained from a community approach to systems biology[END_REF]. Complementary progress in understanding yeast biodiversity, genome variation and genome dynamics is also being achieved at a similar rate through the application of "next generation" genomics (see below).

• Most complete knowledge of genome variation

Rapid technological advances in DNA sequencing and associated informatics have led to the term "next generation" genomics being coined to describe a huge leap in data gathering capacity. The pace of advance in terms of cost per base and speed of genome sequencing, assembly and comparative analysis shows no sign of diminishing. Computational comparative analysis and mathematical descriptions of genome variation and dynamics are providing a deep knowledge base and a broad sampling of yeast diversity to help guide biotechnological exploitation. For example, the Saccharomyces Genome Re-sequencing Project [START_REF] Liti | Population genomics of domestic and wild yeasts[END_REF] has sampled far greater biological diversity than for any other eukaryote, including many strains isolated from "wild" environments as well as those already used across the world in a variety of commercial processes. Yeast genomes are easily and cheaply sequenced, and the genome analysis techniques pioneered with yeasts are of widespread applicability in health and agriculture. Further advances in genomics and systems biology mean that it will become facile to engineer a much wider range of yeast species. The genomic diversity available for future exploitation is discussed below.

Yeast"s extraordinary biological diversity

• Fungal origins and phylogeny

Yeasts are classified biologically as fungi. [START_REF] Kurtzman | The Yeasts -A Taxonomic Study, Fourth Edition p3[END_REF] define yeasts as "…fungi with vegetative states that predominantly reproduce by budding or fission, resulting in growth that is comprised mainly of single cells". Budding yeasts belonging to the ascomycetes group are monophyletic and comprise about 1,000 different species. These species are surprisingly diverse phylogenetically [START_REF] Suh | Phylogenetics of Saccharomycetales, the ascomycete yeasts[END_REF] and have recently been assigned to 14 different lineages on the basis of multigene sequence analysis (Figure1). The remainder of yeast species fall into more distantly-related fungal groupings, most notably the basidiomycetes [START_REF] Scorzetti | Systematics of basidiomycetous yeasts: a comparison of large subunit D1/D2 and internal transcribed spacer rDNA regions[END_REF], which includes an expanding list of yeast species with properties of biotechnological interest (e.g. [START_REF] Zhang | Isolation and characterization of Sporobolomyces sp. LF1 capable of degrading chlorimuron-ethyl[END_REF]. These novel species add significantly to the overall knowledge of yeast phylogenetic diversity and hence to the "gene pool" available for exploitation. It is also clear that many more yeast species remain to be discovered. Beetle guts are proving a particularly rich source of hitherto undescribed species, potentially encompassing a range of novel biocatalytic activities of value to secondgeneration biofuel production [START_REF] Suh | The beetle gut: a hyperdiverse source of novel yeasts[END_REF].

• Evolutionary breadth

In addition to their phylogenetic diversity, whole-genome sequencing of representatives of different genera (Figure 1) has shown that yeasts span a huge evolutionary range. Distributions of amino acid identity between pairs of orthologous proteins indicate that S. cerevisiae is as diverged from Yarrowia lipolytica as Homo sapiens is from the sea squirt, Ciona intestinalis [START_REF] Dujon | Yeasts illustrate the molecular mechanisms of eukaryotic genome evolution[END_REF]. The first organisms comparable to modern yeasts are thought to have evolved over 100 million years ago, coinciding with the evolutionary radiation of flowering plants [START_REF] Wolfe | Molecular evidence for an ancient duplication of the entire yeast genome[END_REF] and around the time that the wholegenome duplication observed in S. cerevisiae is thought to have occurred (Figure 1). However, yeast-like organisms were probably active in the environment long before this time. From this, we conclude that an extraordinary metabolic potential is available for exploitation and the vast majority of this potential has yet to be tapped.

• Sub-species diversity

We are also only just beginning to grasp the equally extraordinary variation that exists within a single yeast species. Large-scale genome sequencing of over seventy S. cerevisiae isolates representative of global population diversity revealed that there are at least four separate geographical lineages worldwide and considerable variation between and within each lineage [START_REF] Liti | Population genomics of domestic and wild yeasts[END_REF]. Detailed examination of strains used commercially also reveals extensive cross hybridisation [START_REF] Dunn | Reconstruction of the genome origins and evolution of the hybrid lager yeast Saccharomyces pastorianus[END_REF], genomic mosaicism [START_REF] Liti | Population genomics of domestic and wild yeasts[END_REF] and sub-species diversity in gene copy number variation, all arising from artificial selection for novel traits [START_REF] Stambuk | Industrial fuel ethanol yeasts contain adaptive copy number changes in genes involved in vitamin B1 and B6 biosynthesis[END_REF]. Similar variation is to be expected within all the other 1,000 or so yeast species described to date and the many more that remain to be discovered.

• Individual cell stochasticity

Even within a yeast culture grown from a single colony, it is becoming clear that considerable biological variation is present. The genome sequence and environmental conditions may remain constant but noise in cellular transcription or translation processes (stochasticity) gives rise to phenotypic individuality. This individuality is manifested in phenomena such as the existence of sub-populations with elevated resistance to environmental challenges e.g. ability to survive in the presence of antimicrobial chemicals [START_REF] Avery | Microbial cell individuality and the underlying sources of heterogeneity Nat[END_REF].

While a systems-level understanding of exactly how all the above variation arises has yet to be achieved, it is already clear that yeasts are an exceptionally diverse biological group with high "evolvability". This helps explain the numerous biotechnological applications which already utilise yeast. It is not our intention here to provide a comprehensive list of such applications, these can be found summarised throughout the yeast-related literature (e.g. [START_REF] Wolf | Nonconventional Yeasts in Biotechnology: A Handbook[END_REF]). Rather, we will select a subset of such applications and discuss the innovative potency of combining yeast systems biology with yeast genome diversity.

Future prospects for yeast biotechnology

• Probiotics

Yeast growth in the human gut is generally thought to be an indicator of ill health. However, there is one yeast strain that is currently used widely as a therapeutic agent [START_REF] Zanello | Saccharomyces boulardii effects on gastrointestinal diseases[END_REF]. The probiotic yeast Saccharomyces boulardii is taxonomically indistinguishable from strains of S. cerevisiae, yet is able to suppress intestinal inflammation caused by a broad range of enteric pathogens. S. boulardii has been shown to be particularly useful in the treatment of antibiotic-induced diarrhoea and Clostridium difficile infection. The yeast strain appears to act by modulating host signalling pathways. Inhibition of interleukin-8 production, which is otherwise induced by C. difficile toxin, leads to reduced intestinal inflammatory responses [START_REF] Zanello | Saccharomyces boulardii effects on gastrointestinal diseases[END_REF]. Since S. boulardii is not typically an enteric organism, understanding its special characteristics and its effects on survival of gut bacteria will provide a useful tool to probe probiotic functions of yeasts in the gut.

Recent metagenomic analyses of gut microflora have suggested that in the region of 0.1% of sequences sampled are of eukaryotic origin [START_REF] Qin | A human gut microbial gene catalogue established by metagenomic sequencing[END_REF]. However, the results of [START_REF] Scanlan | Micro-eukaryotic diversity of the human distal gut microbiota: qualitative assessment using culture-dependent and -independent analysis of faeces[END_REF] indicate that this may be an underestimate. Culturing and DNA sequencing techniques appear to give different results in terms of the eukaryotic microbial species identified. There may therefore be a risk of sampling errors due to the use of DNA extraction techniques which are efficient for bacteria but sub-optimal for fungi. It is also an open question how the reduction in complexity of prokaryotic flora associated with ageing is matched by changes in the eukaryotic flora. However, healthy ageing may well be contingent upon such changes. Furthermore, the recent European Food Safety Authority (EFSA 2009) ruling that health claims for probiotics must be supported by improved characterisation will drive further research into characterisation of yeast-derived bioactive compounds in the gut, with clear opportunities for further biotechnological innovation. Indeed, there is already evidence of strain variation with respect to immunological effects in the mammalian gut (Foligne et al 2010).

• Pharmaceuticals

Yeast strains have been used for many years as cell factories e.g. for insulin production (Pscheidt and Glieder 2008). Innovation in pharmaceutical interventions has been achieved through improved understanding of membrane transporters based on studies in yeast [START_REF] Kim | A combined-cross analysis reveals genes with drug-specific and background-dependent effects on drug sensitivity in Saccharomyces cerevisiae[END_REF]. Yeasts have also become favoured vehicles for the production of recombinant vaccines. Hepatitis B vaccine has been produced in S. cerevisiae for some time [START_REF] Mcaleer | Human hepatitis B vaccine from recombinant yeast[END_REF] and two companies now use this yeast to produce a vaccine against human papilloma virus (HPV) in order to protect against cervical cancer [START_REF] Romanos | Production of a phosphorylated GST::HPV-6 E7 fusion protein using a yeast expression vector and glutathione S-transferase fusions[END_REF][START_REF] Neeper | Expression of the major capsid protein of human papillomavirus type 11 in Saccharomyces cerevisae[END_REF][START_REF] Hofmann | Sequence conservation within the major capsid protein of human papillomavirus (HPV) type 18 and formation of HPV-18 virus-like particles in Saccharomyces cerevisiae[END_REF][START_REF] Bryan | Developing an HPV vaccine to prevent cervical cancer and genital warts[END_REF]. S. cerevisiae is able to assemble capsid subunit proteins into virus-like proteins; however, for the HPV vaccine, it has still proved necessary to re-fold the protein and assemble the particle in vitro. An alternative strategy, of using yeast as a vehicle to deliver vaccines to defined portions of the gut by genetically controlled cell lysis, may be worth pursuing [START_REF] Omara | Conditional cell wall mutants of Saccharomyces cerevisiae as delivery vehicles for therapeutic agents in vivo in the GI tract[END_REF]. Vaccines apart, Pichia pastoris has become the favoured yeast as a vehicle for the production of therapeutic proteins, both due to its higher protein secretion capacity and to the very high cell densities that it achieves in industrial fermenters [START_REF] Cereghino | Heterologous protein expression in the methylotrophic yeast Pichia pastoris[END_REF][START_REF] Li | Expression of recombinant proteins in Pichia pastoris[END_REF][START_REF] Mattanovich | Genome, secretome and glucose transport highlight unique features of the protein production host Pichia pastoris[END_REF][START_REF] Sohn | Genome-scale metabolic model of methylotrophic yeast Pichia pastoris and its use for in silico analysis of heterologous protein production[END_REF].

Yeast has also been subjected to extensive pathway engineering in order to allow it to produce therapeutic agents that defy chemical synthesis and are often difficult to isolate in sufficient quantity from their natural producers, examples include human hydrocortisone [START_REF] Szczebara | Total biosynthesis of hydrocortisone from a simple carbon source in yeast[END_REF] and the antimalarial plant product, artemesinin [START_REF] Ro | Production of the antimalarial drug precursor artemisinic acid in engineered yeast[END_REF]. Problems of inappropriate glycosylation of secreted proteins have been largely overcome (De Pourcq et al 2010). In the future, it can be expected that pathway engineering will be extended to generate products that are either hybrids of compounds produced by other species or to synthesise completely novel products.

• Fuels "First generation" biofuel production suffered a major unintended drawback as competition for raw materials resulted in raised food prices in many parts of the world. "Second generation" bioethanol production seeks to use non-food components of crop plants e.g. wheat straw. However, this aim is complicated by the need to break down complex lignocellulosic plant cell wall material. It is questionable whether cost-effective production of fermentable sugars comparable to the substrates used in first-generation processes can be achieved in the short term. Novel processes will likely depend upon long-term breeding of new crop varieties with modified cell walls (see, for example, [START_REF] Bouton | Molecular breeding of switchgrass for use as a biofuel crop[END_REF]. However, in the interim, yeasts capable of fermenting a wider range of sugars and capable of overcoming fermentation inhibitors present in crude plant cell wall extracts are actively being sought.

A recent example of how yeast"s metabolism might be engineered to overcome a well-known inhibitor of fermentation present in lignocellulosic substrates (acetic acid) is given by Guadalupe [START_REF] Medina | Elimination of glycerol production in anaerobic cultures of a Saccharomyces cerevisiae strain engineered to use acetic acid as an electron acceptor[END_REF]. Their engineered strain also has the highly desirable commercial property of not producing glycerol as a by-product of fermentation. While many other yeast strains have been successfully engineered specifically for commercial biofuel production (e.g. [START_REF] Alper | Engineering yeast transcription machinery for improved ethanol tolerance and production[END_REF], a much broader range of activities is still required. Efficient fermentation of substrates containing glucose, arabinose and xylose in varying ratios and with considerable variation between batches may call for mixed cultures of different yeast species. Bioaugmentation with bacterial species may well have a role in order to break down any oligosaccharides and fermentation inhibitors still remaining after chemical or physical pre-treatment of the raw material. Furthermore, combustion enhancers, such as specific volatiles present in small quantities following fermentation, could be provided by different yeast species as a co-product of mixed fermentations. These could aid the development of "next generation" engines capable of running on a "weaker mix" of bioethanol. Such progress will depend on innovative, robotised selection of genomes, strains and strain mixtures optimised for fermentation of cruder substrates and resistant to batch variations.

Efficient yeast bioprocesses for biofuel production will require that strain development takes a holistic view of how to channel carbon flux toward the desired product. When carbon sources are used which are not natural substrates for yeast, there will often be problems such as cofactor recycle or redox balance to contend with. The classic example is the problem of engineering S. cerevisiae to use pentose sugars from lignocellulose hydolysates.

Here, it is necessary to engineer the organism for optimal uptake of pentoses by recruiting a heterologous transporter [START_REF] Saloheimo | Xylose transport studies with xylose-utilizing Saccharomyces cerevisiae strains expressing heterologous and homologous permeases[END_REF], as well as solve the re-cycling problems due to the different cofactor requirements of the enzymes recruited to perform the first two steps in xylose catabolism [START_REF] Verho | Engineering redox cofactor regeneration for improved pentose fermentation in Saccharomyces cerevisiae[END_REF]. Finally, classic carbon catabolite repression is not observed when cells are grown on xylose [START_REF] Salusjärvi | Regulation of xylose metabolism in recombinant Saccharomyces cerevisiae[END_REF]. All of this means that it is imperative to take a systems biology approach and use a genome-scale metabolic model to direct the metabolic engineering of the production strain [START_REF] Bro | In silico aided metabolic engineering of Saccharomyces cerevisiae for improved bioethanol production[END_REF].

• Minimisation and humanisation

As more and more yeast genomes are sequenced, it is becoming possible to define with increasing accuracy what may be described as the "minimal yeast genome". For example, reduction in the copy number of ribosomal DNA from around 150 copies to less than 40 copies appears to have no effect on cell viability [START_REF] Kobayashi | Expansion and contraction of ribosomal DNA repeats in Saccharomyces cerevisiae: requirement of replication fork blocking (Fob1) protein and the role of RNA polymerase I[END_REF], although it has recently been shown to impact on genome integrity [START_REF] Ide | Abundance of ribosomal RNA gene copies maintains genome integrity[END_REF]. Similarly, not all strains have identical gene complements so strain comparisons enable a "core yeast genome" to be defined. Such information provides the raw material to engineer a yeast cell with a minimal gene complement. With a minimal genome in place and a systems-level understanding of its "wiring diagram" and "design features" it is possible to envisage simple cellular network reprogramming e.g. by engineering modified histone proteins enabling low temperature growth (c.f. Kumar and Wigge 2010) or by introducing phosphorylation sites to modify signalling cascades controlling responses to environmental fluctuations, in order to expand the range of conditions in which yeasts may be used. While the complexity of even a simple eukaryote will mean that unexpected emergent properties will still arise, such cells offer the potential for far more targeted and controllable approaches to achieving novel biotechnological applications.

Furthermore, yeast has still to fulfil its full potential as a medical research tool reducing the need for animal experimentation. Yeast could be used as a "living test-rig" to identify the parameters of human metabolism and determine how these change in disease states. To achieve this, yeast components of specific pathways and systems (mainly enzymes) would be replaced with the coding sequences for their human equivalents under the control of the promoter of the yeast ortholog. This would allow the kinetic parameters of human enzymes to be inferred from changes in the system properties when the system is modulated by, for example, toxins. These observations would be used as the basis for predictions about the behaviour of the human pathway, which could then be tested in human cell lines.

Summary

We have attempted to define ways in which systems biology and biodiversity research complement each other and can be combined to drive innovation in biotechnology. Ever since Hansen"s early contributions, strategic development of culture collections has underpinned biotechnological exploitation of yeast. As noted previously [START_REF] Barnett | A history of research on yeasts 3: Emil Fischer, Eduard Buchner and their contemporaries[END_REF], although Hansen made no obvious scientific advances compared to, for example, Fischer and Buchner of the same era, the latter scientists would have made little progress without the resources provided and the relatively new techniques of microscopy and microbiology that were emerging at the same time. In the post-genome era, culture collections have taken on an expanded role as genetic resource centres. Hitherto untapped biodiversity and screening facilities are being made readily available alongside expertise in genomic analysis. Appropriately formatted collections of sub-species diversity, combined with revolutionary advances in next-generation DNA sequencing, systems and synthetic biology, and the rapidly evolving data resources available as web services, promise to drive a multitude of new applications in fundamental research, biotechnology, sustainable agriculture, and human healthcare.

Acknowledgements

The authors would like to acknowledge financial support from the BBSRC (INR and SGO) and the European Commission through the UNICELLSYS Project (SGO). We also thank Clete Kurtzman and Ken Wolfe for advice and Tom Mayle of the Cambridge University Graphics Department for preparation of Figure 1.

 [START_REF] Kurtzman | Phylogenetic circumscription of Saccharomyces, Kluyveromyces and other members of the Saccharomycetaceae, and the proposal of the new genera Lachancea, Nakaseomyces, Naumovia, Vanderwaltozyma and Zygotorulaspora[END_REF]re-drawn by [START_REF] Scannell | Independent sorting-out of thousands of duplicated gene pairs in two yeast species descended from a whole-genome duplication[END_REF] (see Scannell et al 2007 Supplementary Information: Figure 5) to include information on species with completed genome sequences (bold type; shaded background) and inferred position of divergence due to whole genome duplication (arrow). The figure has been updated to include August 2010 information on additional completed and ongoing yeast genome sequencing projects (bold type; asterisked). Information was taken from www.genolevures.org and http://www.ncbi.nlm.nih.gov/nuccore (search term: fungi[orgn] AND wgs_master [prop]). The latter search identified 31 other yeast species not represented on the tree as having undergone or currently undergoing whole genome sequencing.


Aziz Parosh

Yu-Fang Abdulla

Lorenzo Chen

Lukáš Clemente

Chih-Duo Holík

Richard Hong

Tomas Mayr

Vojnar

Lukáš Clemente

Hong

Ad

Parosh Aziz Abdulla

Yu-Fang Chen

Lorenzo Clemente

Lukáš Holík

Chih-Duo Hong

Richard Mayr

Tomáš Vojnar

Advanced Ramsey-based Büchi Automata Inclusion Testing

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Checking inclusion between finite-state models is a central problem in automata theory. First, it is an intriguing theoretical problem. Second, it has many practical applications. For example, in the automata-based approach to model-checking [START_REF] Vardi | An automata-theoretic approach to automatic program verification[END_REF], both the system and the specification are represented as finite-state automata, and the model-checking problem reduces to testing whether any behavior of the system is allowed by the specification, i.e., to a language inclusion problem.

We consider language inclusion for Büchi automata (BA), i.e., automata over infinite words. While checking language inclusion between nondeterministic BA is computationally hard (PSPACE-complete [START_REF] Kupferman | Verification of fair transition systems[END_REF]), much effort has been devoted to devising approaches that can solve as many practical cases as possible. A naïve approach to language inclusion between BA A and B would first complement the latter into a BA B c , and then check emptiness of L(A) ∩ L(B c ). The problem is that B c is in general exponentially larger than B. Yet, one can determine whether L(A) ∩ L(B c ) = / 0 by only looking at some "small" portion of B c . The Ramsey-based approach [START_REF] Sistla | The Complementation Problem for Büchi Automata with Applications to Temporal Logic[END_REF][START_REF] Fogarty | Büchi Complementation and Size-Change Termination[END_REF][START_REF] Fogarty | Efficient Büchi Universality Checking[END_REF] gives a recipe for doing this. It is a descendant of Büchi's original BA complementation procedure, which uses the infinite Ramsey theorem in its correctness proof.

The essence of the Ramsey-based approach for checking language inclusion between A and B lies in the notion of supergraph, which is a data-structure representing a class of finite words sharing similar behavior in the two automata. Ramsey-based algorithms contain (i) an initialization phase where a set of supergraph seeds are identified, (ii) a search loop in which supergraphs are iteratively generated by composition with seeds, and (iii) a test operation where pairs of supergraphs are inspected for the existence of a counterexample. Intuitively, this counterexample has the form of an infinite ultimately periodic word w 1 (w 2 ) ω ∈L(A)∩L(B c ), where one supergraph witnesses the prefix and the other the loop. While supergraphs themselves are small, and the test in (iii) can be done efficiently, the limiting factor in the basic algorithm lies in the exponential number of supergraphs that need to be generated. Therefore, a crucial challenge in the design of Ramsey-based algorithms is to limit the supergraphs explosion problem. This can be achieved by carefully designing certain subsumption relations [START_REF] Fogarty | Efficient Büchi Universality Checking[END_REF][START_REF] Abdulla | Simulation Subsumption in Ramsey-Based Büchi Automata Universality and Inclusion Testing[END_REF], which allow one to safely discard subsumed supergraphs, thus reducing the search space. Moreover, methods based on minimizing supergraphs [START_REF] Abdulla | Simulation Subsumption in Ramsey-Based Büchi Automata Universality and Inclusion Testing[END_REF] by pruning their structure can further reduce the search space, and improve the complexity of (iii) above.

This paper contributes to the Ramsey-based approach to language inclusion in several ways. [START_REF] Abdulla | Simulation Subsumption in Ramsey-Based Büchi Automata Universality and Inclusion Testing[END_REF] We define a new subsumption relation based on both forward and backward simulation within the two automata. Our notion generalizes the subset-based subsumption of [START_REF] Fogarty | Efficient Büchi Universality Checking[END_REF] and the forward simulation-based subsumption of [START_REF] Abdulla | Simulation Subsumption in Ramsey-Based Büchi Automata Universality and Inclusion Testing[END_REF]. (2) On a similar vein, we improve minimization of supergraphs by employing forward and backward simulation for minimizing supergraphs. [START_REF] Abdulla | When Simulation Meets Antichains: On Checking Language Inclusion of Nondeterministic Finite (Tree) Automata[END_REF] We introduce a method of exploiting forward simulation between the two automata, while previously only simulations internal to each automaton have been considered. (4) Finally, we provide a method to speed up the tests performed on supergraphs by grouping similar supergraphs together in a combined representation and extracting more abstract test-relevant information from it.

The correctness of the combined use of forward and backward simulation turns out to be far from trivial, requiring suitable generalizations of the basic notions of composition and test. Technically, we consider generalized composition and test operations where jumps are allowed-a jump occurring between states related by backward simulation. The proofs justifying the use of jumping composition and test, which can be found in [START_REF] Abdulla | Advanced Ramsey-based Büchi Automata Inclusion Testing[END_REF], are much more involved than in previous works.

We have implemented our techniques and tested them on BA derived from a set of real-world model checking benchmarks [START_REF] Pelánek | BEEM: Benchmarks for Explicit Model Checkers[END_REF] and from the Tabakov-Vardi random model [START_REF] Tabakov | Model Checking Büchi Specifications[END_REF]. The new technique is able to finish many of the difficult problem instances in minutes while the algorithm of [START_REF] Abdulla | Simulation Subsumption in Ramsey-Based Büchi Automata Universality and Inclusion Testing[END_REF] cannot finish them even in one day. All our benchmarks, the source code, and the executable of our implementation are available at http://www.languageinclusion.org/CONCUR2011. Due to limited space, some details of the experiments are deferred to [START_REF] Abdulla | Advanced Ramsey-based Büchi Automata Inclusion Testing[END_REF]. Related work. An alternative approach to language inclusion for BA is given by rankbased methods [START_REF] Kupferman | Weak Alternating Automata Are Not That Weak[END_REF], which provide a different complementation procedure based on a rank-based analysis of rejecting runs. This approach is orthogonal to Ramsey-based algorithms. In fact, while rank-based approaches have a better worst-case complexity, Ramsey-based approaches can still perform better on many examples [START_REF] Fogarty | Efficient Büchi Universality Checking[END_REF]. A subsumption-based algorithm for the rank-based approach has been given in [START_REF] Doyen | Improved Algorithms for the Automata-based Approach to Model Checking[END_REF]. Subsumption techniques have recently been considered also for automata over finite words [START_REF] Wulf | Antichains: A New Algorithm for Checking Universality of Finite Automata[END_REF][START_REF] Abdulla | When Simulation Meets Antichains: On Checking Language Inclusion of Nondeterministic Finite (Tree) Automata[END_REF].

Preliminaries

A Büchi Automaton (BA) A is a tuple (Σ, Q, I, F, δ) where Σ is a finite alphabet, Q is a finite set of states, I ⊆ Q is a non-empty set of initial states, F ⊆ Q is a set of accepting states, and δ ⊆ Q × Σ × Q is the transition relation. A run of A on a word w = σ 1 σ 2 . . . ∈
Σ ω starting in a state q 0 ∈ Q is an infinite sequence q 0 q 1 . . . s.t. (q j-1 , σ j , q j ) ∈ δ for all j > 0. The run is accepting iff q i ∈ F for infinitely many i. The language of A is L(A) = {w | A has an accepting run on w starting from some q 0 ∈ I}.

A path in A on a finite word w = σ 1 . . . σ n ∈ Σ + is a finite sequence q 0 q 1 . . . q n s.t.

∀0 < j ≤ n : (q j-1 , σ j , q j ) ∈ δ. The path is accepting iff ∃0 ≤ i ≤ n : q i ∈ F. For any p, q ∈ Q, let p w F q iff there is an accepting path on w from p to q, and p w q iff there is a (not necessarily accepting) path on w from p to q.

A forward simulation [START_REF] Dill | Checking for language inclusion using simulation preorders[END_REF] on [START_REF] Henzinger | Computing Simulations on Finite and Infinite Graphs[END_REF]. We drop the superscripts when no confusion can arise.

A is a relation R ⊆ Q × Q such that pRr only if p ∈ F =⇒ r ∈ F,
In the rest of the paper, we fix two BA A

= (Σ, Q A , I A , F A , δ A ) and B = (Σ, Q B , I B , F B , δ B ).
The language inclusion problem consists in deciding whether L(A) ⊆ L(B).

It is well known that deciding language inclusion is PSPACE-complete [START_REF] Kupferman | Verification of fair transition systems[END_REF], and that forward simulations [START_REF] Dill | Checking for language inclusion using simulation preorders[END_REF] can be used as an underapproximation thereof. Here, we focus on deciding language inclusion precisely, by giving a complete algorithm.

Ramsey-Based Language Inclusion Testing

Abstractly, the Ramsey-based approach for checking L(A) ⊆ L(B) consists in building a finite set X ⊆ 2 L(A) of fragments of L(A) satisfying the following two properties:

α (covering) X = L(A). β (dichotomy) For all X ∈ X , either X ⊆ L(B) or X ∩ L(B) = / 0.
The covering property ensures that the considered fragments cover L(A), and the dichotomy property states that the fragments are either entirely in L(B) or disjoint from L(B). Moreover, the fragments are chosen such that they can be effectively generated and such that their inclusion in L(B) is easy to test. During the generation of the fragments, it then suffices to test each of them for inclusion in L(B). If this is the case, the inclusion L(A) ⊆ L(B) holds. Otherwise, there is a fragment X ⊆ L(A) \ L(B) s.t. every ω-word w ∈ X is a counterexample to the inclusion of L(A) in L(B).

We now instantiate the above described abstract algorithm by giving primitives for representing fragments of L(A) satisfying the conditions of covering and dichotomy.

Much like in [START_REF] Fogarty | Büchi Complementation and Size-Change Termination[END_REF], we introduce the notion of arcs for satisfying Condition α, the notion of graphs for Condition β, and then we put them together in the notion of supergraphs as to satisfy α + β. Then, we explain that supergraphs can be effectively generated and that the fragment languages they represent can be easily tested for inclusion in L(B).

Condition α: Edges and properness. An edge p, a, q is an element of E A = Q A × {0, 1} × Q A . Its language L p, a, q ⊆ Σ + contains a word w ∈ Σ + iff either (1) a = 1 and p w F q, or (2) a = 0, p w q, but not p w F q. A pair of edges ( q 1 , a, q 2 , q 3 , b, q 4 ) is proper iff q 1 ∈ I A , q 2 = q 3 = q 4 , and b = 1. A pair of edges (x, y) can be used to encode the ω-language Y xy = L(x) • (L(y)) ω . Clearly, if the pair of edges is proper, Y xy ⊆ L(A). Intuitively, the language of a proper pair of edges contains words accepted by lasso-shaped accepting runs starting from q 1 and looping through q 2 . Furthermore, it is clearly the case that one can completely cover L(A) by languages Y xy . Thus, the set X edges = {Y xy | (x, y) is proper } satisfies Condition α.

Condition β: Graphs. A graph g is a subset of edges from E B = Q B × {0, 1} × Q B containing at most one edge for every pair of states. Its language is defined as the set of words over Σ + that are consistent with all the edges of the graph. Namely, w ∈ L(g) iff, for any pair of states p, q ∈ Q B , either (1) p w F q and p, 1, q ∈ g, (2) p w q, ¬(p w F q), and p, 0, q ∈ g, or (3) ¬(p w q) and there is no edge in g of the form p, a, q .

Intuitively, the language of a graph consists of words that all connect any chosen pair of states in the same way (i.e., possibly through an accepting state, through non-accepting states only, or not at all). Let G be the set of all graphs. Not all graphs, however, contain meaningful information, e.g., a graph may contain an edge between states not reachable from each other. Such contradictory information makes the language of a graph empty.

Define

G f = {g ∈ G | L(g) = /
0} as the set of graphs with non-empty languages. It can be shown that the languages of graphs partition Σ + . Like with edges, a pair of graphs (g, h) can be used to encode the ω-language Y gh = L(g) • (L(h)) ω . Intuitively, the pair of graphs g, h encodes all runs in B over the ω-words in Y gh . These runs can be obtained by selecting an edge from g and possibly multiple edges from h that can be connected by their entry/exit states to form a lasso. Since the words in the language of graphs have the same power for connecting states, accepting runs exist for all elements of Y gh or for none of them. The following lemma [START_REF] Sistla | The Complementation Problem for Büchi Automata with Applications to Temporal Logic[END_REF][START_REF] Fogarty | Büchi Complementation and Size-Change Termination[END_REF][START_REF] Fogarty | Efficient Büchi Universality Checking[END_REF] shows that the set X graphs =

{Y gh | g, h ∈ G f } satisfies Condition β. Lemma 1. For graphs g, h, either Y gh ⊆ L(B) or Y gh ∩ L(B) = / 0.
Condition α + β: Supergraphs. We combine edges and graphs to build more complex objects satisfying, at the same time, Conditions α and β. A supergraph is a pair g = x, g ∈ E A × G. 1 A supergraph is only meaningful if the information in the edgepart is consistent with that in the graph-part. To this end, let L(g

) = L(x) ∩ L(g) and let S f = {g | L(g) = /
0} be the set of supergraphs with non-empty language. For two supergraphs g = x, g and h = y, h , the pair

(g, h) is proper if the edge-pair (x, y) is proper. Let Y gh = L(g) • (L(h)) ω . Notice that Y gh ⊆ Y xy ∩Y gh . Therefore, since Y gh sat- isfies Condition β, so does Y gh ⊆ Y gh .
For Condition α, we show that Y xy can be covered by a family of languages of the form Y x,g y,h . This is sound since Y x,g y,h ⊆ Y xy for any g, h. Completeness follows from the lemma below, stating that every word w ∈ Y xy lies in a set of the form Y x,g y,h . It is proved by a Ramsey-based argument.

Lemma 2. For proper edges (x, y) and w ∈ Y xy , there exist graphs g, h s.t. w ∈ Y x,g y,h .

Thus, Y xy can be covered by X xy = {Y gh | g, h ∈ G f , g = x, g , h = y, h }. Since X edges covers L(A), and each Y xy ∈ X edges can be covered by X xy , it follows that X = {Y gh | g, h ∈ S f , (g, h) is proper} covers L(A). Thus, X fulfills α + β.

Generating and Testing Supergraphs. While supergraphs in S f are a convenient syntactic object for manipulating languages in X , testing that a given supergraph has nonempty language is expensive (PSPACE-complete). In [START_REF] Jones | The Size-Change Principle for Program Termination[END_REF], this problem is elegantly solved by introducing a natural notion of composition of supergraphs, which preserves non-emptiness: The idea is to start with a (small) set of supergraphs which have nonempty language by construction, and then to obtain S f by composing supergraphs until no more supergraphs can be generated.

For a BA C and a symbol σ ∈ Σ, let E σ C = { p, a, q | (p, σ, q) ∈ δ C , (a = 1 ⇐⇒ p ∈ F ∨ q ∈ F
)} be the set of edges induced by σ. The initial seed for the procedure is given by one-letter supergraphs in

S 1 = σ∈Σ {(x, E σ B ) | x ∈ E σ A }.
Notice that S 1 ⊆ S f by construction. Next, two edges x = p, a, q and y = q , b, r are composable iff q = q . For composable edges x and y, let x; y = p, max(a, b), r . Further, the composition g; h of graphs g and h is defined as follows: p, c, r ∈ g; h iff there is a state q s.t. p, a, q ∈ g and q, b, r ∈ h, and c = max q∈Q {max(a, b) | p, a, q ∈ g, q, b, r ∈ h}. Then, supergraphs g = x, g and h = y, h are composable iff x, y are composable, and their composition is the supergraph g; h = x; y, g; h . Notice that S f is closed under composition, i.e., g, h ∈ S f =⇒ g; h ∈ S f . Composition is also complete for generating S f :

Lemma 3. [1] A supergraph g is in S f iff ∃g 1 , . . . , g n ∈ S 1 such that g = g 1 ; . . . ; g n .
Now that we have a method for generating all relevant supergraphs, we need a way of checking inclusion of (supergraphs representing) fragments of L(A) in L(B). Let (g, h) be a (proper) pair of supergraphs. By the dichotomy property, Y gh ⊆ L(B) iff Y gh ∩L(B) = / 0. We test the latter condition by the so-called double graph test: For a pair of supergraphs (g, h), DGT(g, h) iff, whenever (g, h) is proper, then LFT(g, h). Here, LFT is the so-called lasso-finding test: Intuitively, LFT checks for a lasso with a handle in g and an accepting loop in h. Formally, LFT(g, h) iff there is an edge p, a 0 , q 0 ∈ g and an infinite sequence of edges q 0 , a 1 , q 1 , q 1 , a 2 , q 2 , . . . ∈ h s.t. p ∈ I and a j = 1 for infinitely many j's.

Lemma 4. [1] L(A) ⊆ L(B) iff for all g, h ∈ S f , DGT(g, h).
Basic Algorithm [START_REF] Fogarty | Büchi Complementation and Size-Change Termination[END_REF]. The basic algorithm for checking inclusion enumerates all supergraphs from S f by extending supergraphs on the right by one-letter supergraphs from S 1 ; that is, a supergraph g generates new supergraphs by selecting some h ∈ S 1 and building g; h. Then, L(A) ⊆ L(B) holds iff all the generated pairs pass the DGT.

Intuitively, the algorithm processes all lasso-shaped runs that can be used to accept some words in A. These runs are represented by the edge-parts of proper pairs of generated supergraphs. For each such run of A, the algorithm uses LFT to test whether there is a corresponding accepting run of B among all the possible runs of B on the words represented by the given pair of supergraphs. These latter runs are encoded by the graph-parts of the respective supergraphs.

The basic algorithm of Section 3 is wasteful for two reasons. First, not all edges in the graph component of a supergraph are needed to witness a counterexample to inclusion: Hence, we can reduce a graph by keeping only a certain subset of its edges (Optimization 1). Second, not all supergraphs need to be generated and tested: We show a method which safely allows the algorithm to discard certain supergraphs (Optimization 2). Both optimizations rely on various notions of subsumption, which we introduce next.

Given two edges x = p, a, q and y = r, b, s , we say that y subsumes x, written x y, if p = r, a ≤ b, and q = s; that x forward-subsumes y, written x f y, if p = r, a ≤ b, and q f s; that x backward-subsumes y, written x b y, if p b r, a ≤ b, and q = s; and that x forward-backward-subsumes y, written x fb y, if p b r, a ≤ b, and q f s. We lift all the notions of subsumption to graphs: For any z ∈ {f, b, fb, } and for graphs g and h, let g z h iff, for every edge x ∈ g, there exists an edge y ∈ h s.t. x z y. Since the simulations f and b are preorders, all subsumptions are preorders. We define backward and forward-backward subsumption equivalence as b = b ∩ -1 b and fb = fb ∩ -1 fb , respectively.

Optimization 1: Minimization of Supergraphs

The first optimization concerns the structure of individual supergraphs. Let g = x, g ∈ S be a supergraph, with g its graph-component. We minimize g by deleting edges therein which are subsumed by fb -larger ones. That is, whenever we have x fb y for two edges x, y ∈ g, we remove x and keep y. Intuitively, subsumption-larger arcs contribute more to the capability of representing lassoes since their right and left endpoints are f / blarger, respectively, and have therefore a richer choice of possible futures and pasts. Subsumption smaller arcs are thus redundant, and removing them does not change the capability of g to represent lassoes in B. Formally, we define a minimization operation Min mapping a supergraph g = x, g to its minimized version Min(g) = x, Min(g) where Min(g) is the minimization applied to the graph-component. 2Definition 1. For two graphs g and h, let g h iff (1) g h and (2) h fb g. For supergraphs g = x, g and h = y, h , let g h iff x = y and g h. A minimization of graphs is any function Min such that, for any graph h, Min(h) h.

Point 1 in the definition of allows some edges to be erased or their label decreased. Point 2 states that only subsumed arcs can be removed or have their label decreased. Note also that, clearly, Min(h) h holds for any supergraph h. Finally, note that Min is not uniquely determined: First, there are many candidates satisfying Min(h) h. Yet, an implementation will usually remove a maximal number of edges to keep the size of graphs to a minimum. Second, even if we required Min(h) to be a -smallest element (i.e., no further edge can be removed), the minimization process might encounter fbequivalent edges, and in this case, we do not specify which ones get removed. Therefore, we prove correctness for any minimization satisfying Min(h) h.

Intuitively, a minimized supergraph g can be seen as a small representative of all supergraphs h ∈ G f with g h, and of all the fragments of L(A) encoded by them.

Using representatives allows us to deal with a smaller number of smaller supergraphs.

We now explain how (sufficiently many) representatives encoding fragments of L(A) can be generated and tested for inclusion in L(B).

Generating representatives of supergraphs. We need to create a representative of each supergraph in S f by composing representatives only. Let g = x, g and h = y, h be two composable supergraphs, representing g = x, g and h = y, h , respectively. If graph composition were -monotone, i.e., g; h g ; h , then we would be done. However, graph composition is not monotone: The reason is that some composable edges e ∈ g and f ∈ h may be erased by minimization, and be represented by some ê ∈ g and f ∈ h instead, with e fb ê and f fb f . But now, ê and f are not necessarily composable anymore. Thus, g; h g ; h . We solve this problem in two steps: We allow composition to jump to b -larger states (Def. 2), and relax the notion of representative (Def. 3).

Definition 2. Given graphs g, h ∈ G, their jumping composition g b h contains an edge p, c, r ∈ g b h iff there are edges p, a, q ∈ g, q , b, r ∈ h s.t. q b q , and c = max q,q {max(a, b) | p, a, q ∈ g, q , b, r ∈ h, q b q }. For two composable supergraphs g = x, g and h = y, h , let g b h = x; y, g b h .

Jumping composition alone does not yet give the required monotonicity property. The problem is that g b h is not necessarily a minimized version of g ; h , but it is only a minimized version of something b -equivalent to g ; h . This leads us to the following more liberal notion of representatives, which is based on modulo the equivalence b , and for which Lemma 5 proves the required monotonicity property. Definition 3. A graph g ∈ G is a representative of a graph h ∈ G f , denoted g h, iff there exists h ∈ G such that g h b h. For supergraphs g = x, g , h = y, h ∈ S, we say that g is a representative of h, written g h, iff x = y and g h. Let S R = {g | ∃h ∈ S f . g h} be the set of representatives of supergraphs. Lemma 5. For supergraphs g, h ∈ S R and g , h ∈ S f , if g g , h h and g , h are composable, then g, h are composable and g b h g ; h and g b h ∈ S R . Lemma 6. Let f ∈ S, g ∈ S R , and h ∈ S f . If f g and g h, then f h (and thus f ∈ S R ). In particular, the statement holds when f = Min(g).

Lemmas 5, 6, and 3 imply that creating supergraphs by b -composing representatives, followed by further minimization, suffices to create a representative of each supergraph in S f . This solves the problem of generating representatives of supergraphs.

Weak properness and Relaxed DGT. We now present a relaxed DGT proposed in [START_REF] Abdulla | Simulation Subsumption in Ramsey-Based Büchi Automata Universality and Inclusion Testing[END_REF], which we further improve below. The idea is to weaken the properness condition in order to allow more pairs of supergraphs to be eligible for LFT on their graph part. This may lead to a quicker detection of a counterexample. Weak properness is sound since it still produces fragments Y gh ⊆ L(A) as required by Condition α. Completeness is guaranteed since properness implies weak properness. Definition 4. (adapted from [START_REF] Abdulla | Simulation Subsumption in Ramsey-Based Büchi Automata Universality and Inclusion Testing[END_REF]) A pair of edges ( p, a, q , r, b, s ) is weakly proper iff p ∈ I A , r f q, r f s, and b = 1, 3 and a pair of supergraphs (g = x, g , h = y, h ) is weakly proper when (x, y) is weakly proper. Supergraphs g, h pass the relaxed double graph test, denoted RDGT(g, h), iff whenever (g, h) is weakly proper, then LFT(g, h).

Lemma 7.

[1] L(A) ⊆ L(B) iff for all g, h ∈ S f , RDGT(g, h).

Testing representatives of supergraphs. We need a method for testing inclusion in L(B) of the fragments of L(A) encoded by representatives of supergraphs that is equivalent to testing inclusion of fragments of L(A) encoded by the represented supergraphs. As with composition, minimization is not compatible with such testing since edges needed to find loops may be erased during the minimization process. Technically, this results in the LFT (and therefore RDGT) not being -monotone. Therefore, we generalize the LFT by allowing jumps to b -larger states, in a similar way as with b . Lemma 8 establishes the required monotonicity property. Definition 5. A pair of graphs (g, h) passes the jumping lasso-finding test, denoted LFT b (g, h), iff there is an edge p, a 0 , q 0 in g and an infinite sequence of edges q 0 , a 1 , q 1 , q 1 , a 2 , q 2 , . . . in h s.t. p ∈ I, q i b q i for all i ≥ 0, and a j = 1 for infinitely many j's. A pair of supergraphs (g, h) passes the jumping relaxed double graph test, denoted RDGT b (g, h), iff whenever (g, h) is weakly proper, then LFT b (g, h). Lemma 8. For any g, h ∈ S R and g , h ∈ S f such that g g and h h , it holds that RDGT b (g, h) ⇐⇒ RDGT(g , h ).

Algorithm with minimization. By Lemma 8, RDGT b on representatives is equivalent to RDGT on the represented supergraphs. Together with Lemma 7, this means that it is enough to generate a representative of each supergraph from S f , and test all pairs of the generated supergraphs with RDGT b . Thus, we have obtained a modification of the basic algorithm which starts from minimized 1-letter supergraphs in Min(S 1 ) = {Min(g) | g ∈ S 1 }, and constructs new supergraphs by b -composing already generated supergraphs with Min(S 1 ) on the right. New supergraphs are further minimized with Min. Inclusion holds iff all pairs of generated supergraphs pass RDGT b .

Optimization 2: Discarding Subsumed Supergraphs

The second optimization gives a rule for discarding supergraphs subsumed by some other supergraph. This is safe in the sense that if a subsumed supergraph can yield a counterexample to language inclusion, then also the subsuming one can yield a counterexample. We present an improved version of the subsumption from [START_REF] Abdulla | Simulation Subsumption in Ramsey-Based Büchi Automata Universality and Inclusion Testing[END_REF]. The new version uses both f and b on the B part of supergraphs instead of f only. This allows us to discard significantly more supergraphs than in [START_REF] Abdulla | Simulation Subsumption in Ramsey-Based Büchi Automata Universality and Inclusion Testing[END_REF], as illustrated in Section 8. Definition 6. We say that a supergraph g = x, g subsumes a supergraph g = y, g , written g fb g , iff y f x and g fb g .

Intuitively, if y f x, then x has more power for representing lassoes in A than y since, by the properties of forward simulation, it has a richer choice of possible forward continuations in A. On the other hand, g fb g means that g has more chance of representing lassoes in B than g: In fact, g contains edges that have a richer choice of backward continuations (due to the b on the left endpoints of the edges) as well as a richer choice of forward continuations (due to the f on the right endpoints). Thus, it is more likely for g than for g to lead to a counterexample to language inclusion. This intuition is confirmed by the lemma below, stating the fb -monotonicity of RDGT b . Lemma 9. For supergraphs g, h ∈ S R and g , h ∈ S, if g fb g and h fb h , then RDGT b (g, h) ⇒ RDGT b (g , h ).

Therefore, no counterexample is lost by testing only fb -smaller supergraphs. To show that we can completely discard fb -larger supergraphs, we need to show that subsumption is compatible with composition, i.e., that descendants of larger supergraphs are (eventually) subsumed by descendants of smaller ones. Ideally, we would achieve this by showing the following more general fact: For two composable representatives g , h ∈ S R that are subsumed by supergraphs g and h, respectively, the composite supergraph g b h subsumes g b h . The problem is that subsumption does not preserve composability: Even if g , h are composable, this needs not to hold for g, h.

We overcome this difficulty by taking into account the specific way supergraphs are generated by the algorithm. Since we only generate new supergraphs by composing old ones on the right with 1-letter minimized supergraphs, we do not need to show that arbitrary composition is fb -monotone. Instead, we show that, for representatives g, g ∈ S R and a 1-letter minimized supergraph h ∈ Min(S 1 ), if g subsumes g , then there will always be a supergraph h available which is composable with g such that g b h subsumes g b h . Thus, we can safely discard g from the rest of the computation. Lemma 10. For any g, g ∈ S R with g fb g and h ∈ Min(S 1 ) such that g and h are composable, there exists ĥ ∈ Min(S 1 ) such that for all h ∈ S R with h fb ĥ, g is composable with h and g b h fb g b h .

Algorithm with minimization and subsumption. We have obtained a modification of the algorithm with minimization. It starts with a subset Init ⊆ Min(S 1 ) of fb -smallest minimized one-letter supergraphs. New supergraphs are generated by b -composition on the right with supergraphs in Init, followed by minimization with Min. Generated supergraphs that are fb -larger than other generated supergraphs are discarded. The inclusion holds iff all pairs of generated supergraphs that are not discarded pass RDGT b . (An illustration of a run of the algorithm can be found in [START_REF] Abdulla | Advanced Ramsey-based Büchi Automata Inclusion Testing[END_REF].)

5 Using Forward Simulation Between A and B Previously, we showed that some supergraphs can safely be discarded because some fb -smaller ones are retained, which preserves the chance to find a counterexample to language inclusion. Our subsumption relation fb is based on forward/backward simulation on A and B. In order to use forward simulation between A and B, we describe a different reason to discard supergraphs. Generally, supergraphs can be discarded because they can neither find a counterexample to inclusion (i.e., always pass the RDGT) nor generate any supergraph that can find a counterexample. However, the RDGT is asymmetric w.r.t. the left and right supergraph. Thus, a supergraph that is useless (i.e., not counterexample-finding) in the left role is not necessarily useless in the right role (and vice-versa). The following condition C is sufficient for a supergraph to be useless on the left. Moreover, C is efficiently computable and compatible with subsumption. Therefore, its use preserves the soundness and completeness of our algorithm. Definition 7. For g= p, a, q , g ∈ S, C(g

) iff p / ∈ I A ∨(∃ r, b, s ∈ g. r ∈ I B ∧q AB f s).
The first part p / ∈ I A of the condition is obvious because paths witnessing counterexamples to inclusion must start in an initial state. The second part (∃ r, b, s ∈ g. r ∈ I B , q AB f s) uses forward-simulation AB f between A and B to witness that neither this supergraph nor any other supergraph generated from it will find a counterexample when used on the left side of the RDGT. It might still be needed for tests on the right side of the RDGT though. Instead of AB f , every relation implying language inclusion would suffice, but (as mentioned earlier) simulation preorder is efficiently computable while inclusion is PSPACE-complete. The following lemma shows the correctness of C.

Lemma 11. ∀g, h ∈ S R . C(g) ⇒ RDGT b (g, h).
C is fb -upward-closed and closed w.r.t. right extensions. Hence, it is compatible with subsumption-based pruning of the search space and with the employed incremental construction of supergraphs (namely, satisfaction of the condition is inherited to supergraphs newly generated by right extension with one-letter supergraphs).

Lemma 12. Let g, h ∈ S s.t. g fb h. Then C(g) ⇒ C(h).

Lemma 13. Let g ∈ S R , h ∈ Min(S 1 ) be composable. Then C(g) ⇒ C(g b h).

In principle, one could store separate sets of supergraphs for use on the left/right in the RDGT, respectively. However, since all supergraphs need to be used on the right anyway, a simple flag is more efficient. We assign the label L to a supergraph to indicate that it is still useful on the left in the RDGT. If a supergraph satisfies condition C, then the L-label is removed. The algorithm counts the number of stored supergraphs that still carry the L-label. If this number drops to zero, then (1) it will remain zero (by Lemma 13), and (2) no RDGT will ever find a counterexample: In this case, the algorithm can terminate early and report inclusion. In the special case where forwardsimulation holds even between the initial states of A and B, condition C is true for every generated supergraph. Thus, all L-labels are removed and the algorithm terminates immediately, reporting inclusion. Of course, condition C can also help in other cases where simulation does not hold between initial states but "more deeply" inside the automata.

The following lemma shows that if some supergraph g can find a counterexample when used on the left in the RDGT, then at least one of its 1-letter right-extensions can also find a counterexample. Intuitively, the counterexample has the form of a prefix followed by an infinite loop, and the prefix can always be extended by one step. E.g., the infinite words xy(abc) ω and xya(bca) ω are equivalent. This justifies the optimization in line 15 of our algorithm (cf. [START_REF] Abdulla | Advanced Ramsey-based Büchi Automata Inclusion Testing[END_REF]). Lemma 14. Let g, h ∈ S R . If ¬RDGT b (g, h), then there exists a fb -minimal supergraph f in Min(S 1 ) and e ∈ S R s.t. ¬RDGT b (g b f, e). 4Since many supergraphs share the same graph for B, they can be more efficiently represented by a combined structure that we call a metagraph. Moreover, metagraphs allow to define a new RDGT where several A-edges jointly witness a counterexample to inclusion, so that counterexamples can be found earlier than with individual supergraphs.

A metagraph is a structure (X, g) where X ⊆ E A is a set of A-edges and g ∈ G B . The metagraph (X, g) represents the set of all supergraphs x, g with x ∈ X. The L-labels of supergraphs then become labels of the elements of X since the graph g is the same.

We lift basic concepts from supergraphs to metagraphs. For every character σ ∈ Σ, there is exactly one single-letter metagraph

(E σ A , E σ B ). Let M 1 = {(E σ A , E σ B )| σ ∈ Σ}.
Thus, the set of single-letter metagraphs M 1 represents all single-letter supergraphs in S 1 . The function RightExtend defines the composition of two metagraphs such that RightExtend((X, g), (Y, h)) = (X;Y, g b h), which is the metagraph containing the supergraphs that are b -right extensions of supergraphs contained in (X, g) by supergraphs contained in (Y, h). The L-labels of the elements z ∈ X;Y are assigned after testing condition C. The function Min f is defined on sets X ⊆ E A s.t. Min f (X) contains the fminimal edges of X. If some edges are f -equivalent, then Min f (X) contains just any of them. Let Min M (X, g) = (Min f (X), Min(g)). Thus, Min M (X, g) contains exactly one representative of every fb equivalence class of the fb -minimal supergraphs in (X, g).

It is not meaningful to define subsumption for metagraphs. Instead, we need to remove certain supergraphs (i.e., A-edges) from some metagraph if another metagraph contains a fb -smaller supergraph. If no A-edge remains, i.e., X = / 0 in (X, g), then this metagraph can be discarded. This is the purpose of introducing the function Clean: It takes two metagraphs (X, g) and (Y, h), and it returns a metagraph (Z, g) that describes all supergraphs from (X, g) for which there is no fb -smaller supergraph in (Y, h). Formally, if h fb g, then x ∈ Z iff x ∈ X and ∃y ∈ Y s.t. x f y. Otherwise, if h fb g, then Z = X. Now we define a generalized RDGT on metagraphs. Definition 8. A pair of sets of A-edges X,Y ⊆ E A passes the forward-downward jumping lasso-finding test, denoted LFT f (X,Y ), iff there is an arc p, a 0 , q 0 in X (with the L-label) and an infinite sequence of arcs q 0 , a 1 , q 1 , q 1 , a 2 , q 2 , . . . in Y s.t. p ∈ I A , q i f q i for all i ≥ 0, and a j = 1 for infinitely many j's.

Definition 9. RDGT M b ((X, g), (Y, h)) iff, whenever LFT f (X,Y ), then LFT b (g, h).
The following lemma shows the soundness of the new RDGT.

Lemma 15. Let (X, g), (Y, h) be metagraphs where all contained supergraphs are in

S R . If ¬RDGT M b ((X, g), (Y, h)), then L(A) ⊆ L(B).
If there are x ∈ X, y ∈ Y s.t. ¬RDGT b ( x, g , y, h ), then ¬RDGT M b ((X, g), (Y, h)), by Definitions 4, 8, and 9. Thus the completeness of the new RDGT follows already from Lemmas 7 and 8. Checking RDGT M b ((X, g), (Y, h)) can be done very efficiently for large numbers of metagraphs, by using an abstraction technique that extracts testrelevant information from the metagraphs and stores it separately (cf. [START_REF] Abdulla | Advanced Ramsey-based Büchi Automata Inclusion Testing[END_REF]). three classes, according to whether (1) simulation holds, (2) inclusion holds (but not simulation), and (3) inclusion does not hold. See, resp., Tables 1,2, and 3. On average, the newly proposed approach using all the mentioned options produces the best result.

In the second experiment, we use the Tabakov-Vardi random model6 with fixed alphabet size 2. There are two parameters, transition density (td; average number of transitions per state and alphabet symbol) and acceptance density (ad; percentage of accepting states). The results of a complete test for many parameter combinations and automata of size 15 can be found in [START_REF] Abdulla | Advanced Ramsey-based Büchi Automata Inclusion Testing[END_REF]. Its results can be summarized as follows. In those cases where simulation holds between initial states, the time needed is negligible. Also the time needed to find counterexamples is very small. Only the "inclusion" cases are interesting. Based on the results presented in [START_REF] Abdulla | Advanced Ramsey-based Büchi Automata Inclusion Testing[END_REF], we picked two configurations (Hard: td=2, ad=0.1, size=30) and (Easy, but nontrivial: td=3, ad=0.6, size=50) for an experiment with larger automata. Both configurations have a substantial percentage of the interesting "inclusion" cases. The results can be found in Table 4.

Conclusions

We have presented an efficient method for checking language inclusion for Büchi automata. It augments the basic Ramsey-based algorithm with several new techniques such as the use of weak subsumption relations based on combinations of forward and backward simulation, the use of simulation relations between automata in order to limit the search space, and methods for eliminating redundant tests in the search procedure. We have performed a wide set of experiments to evaluate our approach, showing its practical usefulness. An interesting direction for future work is to characterize the roles of the different optimizations in different application domains. Although their overall effect is to achieve a much better performance compared to existing methods, the contribution of each optimization will obviously vary from one application to another. Such a characterization would allow a portfolio approach in which one can predict which optimization would be the dominant factor on a given problem. In the future, we also plan to implement both the latest rank-based and Ramsey-based approaches in a uniform way and thoroughly investigate how they behave on different classes of automata.

Table 3 .

 3 Language inclusion checking on mutual exclusion protocols. Language inclusion does not hold. Note that the new algorithm uses a different search strategy (BFS) than the alg. in[START_REF] Abdulla | Simulation Subsumption in Ramsey-Based Büchi Automata Universality and Inclusion Testing[END_REF].

	Protocol	A Trans. States Trans. States of [1] default -b -b -qr -b -qr -c B Algorithm New Algorithm
	BakeryV3 2090 1149 2697 1506 12m19s	5s	6s	16s	15s
	FischerV5 3850 1532 1420 643 7h28m 1m6s 1m47s 39s	36s
	PhilsV2	482 161 212	80	1.1s	0.7s 0.8s	1s	1s
	PhilsV3	464 161 212	80	1s	0.7s 0.8s 1.2s	1.1s
	PhilsV4	482 161 464 161	10.7s	3.8s 4.5s 4.8s	4.8s

Table 4 .

 4 Results of the Tabakov-Vardi experiments on two selected configurations. In each case, we generated 100 random automata and set the timeout to one hour. The new algorithm found more cases with simulation between initial states because the option -qr (do fw/bw quotienting repeatedly) may change the forward simulation in each iteration. In the "Hard" case, most of the timeout instances probably belong to the category "inclusion" (Inc).

		Hard: td=2, ad=0.1, size=30	Easy, but nontrivial: td=3, ad=0.6, size=50
		The Algorithm of [1] New Algorithm The Algorithm of [1] New Algorithm
	Sim	1%, 32m42s	2%, 0.025s	13%, 2m5s	21%, 0.14s
	Inc	16%, 43m	20%, 30m42s	68%, 26m14s	64%, 6m12s
	nInc	49%, 0.17s	49%, 0.2s	15%, 0.3s	15%, 0.3s
	TO	34%	29%	4%	0%

The definition of supergraph given here is slightly different from[START_REF] Fogarty | Büchi Complementation and Size-Change Termination[END_REF][START_REF] Abdulla | Simulation Subsumption in Ramsey-Based Büchi Automata Universality and Inclusion Testing[END_REF], where the edge-part is just a pair of states (p, q). Having labels allows us to give a notion of properness which does not require to have q ∈ F.

In[START_REF] Abdulla | Simulation Subsumption in Ramsey-Based Büchi Automata Universality and Inclusion Testing[END_REF], we used f for minimization. The theory allowing the use of fb is significantly more involved, but as as shown in Section 8, the use of fb turns out to be much more advantageous.

We note that instead of testing r f q, testing inclusion of the languages of the states is sufficient. Furthermore, instead of testing r f s, one can test for delayed simulation, but not for language inclusion. See[START_REF] Abdulla | Advanced Ramsey-based Büchi Automata Inclusion Testing[END_REF] for details.

A slightly modified version, presented in[START_REF] Abdulla | Advanced Ramsey-based Büchi Automata Inclusion Testing[END_REF], holds for the version of the RDGT mentioned in the footnote on Definition 4.

The models in[START_REF] Pelánek | BEEM: Benchmarks for Explicit Model Checkers[END_REF] are based on guarded commands. We derive variants from them by randomly weakening or strengthening the guard of some commands.

Note that automata generated by the Tabakov-Vardi model are very different from a controlflow graph of a program. They are almost unstructured, and thus on average the density of simulation is much lower. Hence, we believe it is not a fair evaluation benchmark for algorithms aimed at program verification. However, since it was used in the evaluation of most previous works on language inclusion testing, we also include it as one of the evaluation benchmarks.

This work was supported by Royal Society grant JP080268, the UPMARC project, the CON-NECT project, National Science Council of Taiwan project no. 99-2218-E-001-002-MY3, the Czech Science Foundation (projects P103/10/0306 and 102/09/H042), the Czech Ministry of Education (projects COST OC10009 and MSM 0021630528), and the BUT FIT project FIT-S-11-1.

Algorithm 1 describes our inclusion testing algorithm. The function Clean is extended to sets of metagraphs in the standard way and implemented in procedures Clean 1 and Clean 3 in which the result overwrites the first argument (the two procedures differ in the role of the first argument, and Clean 3 in addition discards empty metagraphs). Lines 1-6 compute the metagraphs which contain the subsumption-minimal 1-letter supergraphs. Lines 7-10 initialize the set Next with these metagraphs and assign the correct labels by testing condition C. L(x) denotes that the A-arc x is labeled with L. Lines 11-21 describe the main loop. It runs until Next is empty or there are no more L-labels left. In the main loop, metagraphs are tested (lines [START_REF] Kupferman | Verification of fair transition systems[END_REF][START_REF] Kupferman | Weak Alternating Automata Are Not That Weak[END_REF] and then moved from Next to Processed without the L-label (line 15). Moreover, new metagraphs are created and some parts of them discarded by the Clean operation (lines 16-21). Extra bookkeeping is needed to handle the case where L-labels are regained by supergraphs in Processed in line 19 (see Clean 2 in [START_REF] Abdulla | Advanced Ramsey-based Büchi Automata Inclusion Testing[END_REF]).

Algorithm 1: Inclusion Checking with Metagraphs

Pick and remove a metagraph (X, g) from Next;

4 Clean 1 ((X, g), Init);

Clean 3 (Init, (X, g)); Add (X, g) to Init;

Pick a metagraph (X, g) from Next and remove (X, g) from Next;

15 Create (X , g) from (X, g) by removing the L-labels from X and add (X , g) to Processed;

Experimental Results

We have implemented the proposed inclusion-checking algorithm in Java (the implementation is available at http://www.languageinclusion.org/CONCUR2011) and tested it on automata derived from (1) mutual exclusion protocols [START_REF] Pelánek | BEEM: Benchmarks for Explicit Model Checkers[END_REF] and (2) the Tabakov-Vardi model [START_REF] Tabakov | Model Checking Büchi Specifications[END_REF]. We have compared the performance of the new algorithm with the one in [START_REF] Abdulla | Simulation Subsumption in Ramsey-Based Büchi Automata Universality and Inclusion Testing[END_REF] (which only uses supergraphs, not metagraphs, and subsumption and minimization based on forward simulation on A and on B), and found it better on average, and, in particular, on difficult instances where the inclusion holds. Below, we present a condensed version of the results. Full details can be found in [START_REF] Abdulla | Advanced Ramsey-based Büchi Automata Inclusion Testing[END_REF].

In the first experiment, we inject artificial errors into models of several mutual exclusion protocols from [START_REF] Pelánek | BEEM: Benchmarks for Explicit Model Checkers[END_REF] 5 , translate the modified versions into BA, and compare the sequences of program states (w.r.t. occupation of the critical section) of the two versions. For each protocol, we test language inclusion L(A) ⊆ L(B) of two variants A and B. We use a timeout of 24 hours and a memory limit of 4GB. We record the running time and indicate a timeout by ">24h". We compare the algorithm from [START_REF] Abdulla | Simulation Subsumption in Ramsey-Based Büchi Automata Universality and Inclusion Testing[END_REF] against its various improvements proposed above. The basic new setting (denoted as "default" in the results) uses forward simulation as in [START_REF] Abdulla | Simulation Subsumption in Ramsey-Based Büchi Automata Universality and Inclusion Testing[END_REF] together with metagraphs from Section 6 (and some further small optimizations described in [START_REF] Abdulla | Advanced Ramsey-based Büchi Automata Inclusion Testing[END_REF]). Then, we gradually add the use of backward simulation proposed in Section 4 (denoted by -b in the results) and forward simulation between A and B from Section 5 (denoted by -c, finally yielding the algorithm of Section 7). We also consider repeated quotienting w.r.t. forward/backward-simulation-equivalence before starting the actual inclusion checking (denoted by -qr), while the default does quotienting w.r.t. forward simulation only. In order to better show the capability of the new techniques, the results are categorized into