Search

This extended abstract is about an effort to build a formal description of a triangulation algorithm starting with a naive description of the algorithm where triangles, edges, and triangulations are simply given as sets and the most complex notions are those of boundary and separating edges. When performing proofs about this algorithm, questions of symmetry appear and this exposition attempts to give an account of how these symmetries can be handled. All this work relies on formal developments made with Coq and the mathematical components library.

We describe how to compute very far decimals of $$\pi$$ and how to provide formal guarantees that the decimals we compute are correct. In particular, we report on an experiment where 1 million decimals of $$\pi$$ and the billionth hexadecimal (without the preceding ones) have been computed in a formally verified way. Three methods have been studied, the first one relying on a spigot formula to obtain at a reasonable cost only one distant digit (more precisely a hexadecimal digit, because the numeration basis is 16) and the other two relying on arithmetic-geometric means. All proofs and computations can be made inside the Coq system. We detail the new formalized material that was necessary for this achievement and the techniques employed to guarantee the accuracy of the computed digits, in spite of the necessity to work with fixed precision numerical computation., Comment: Journal of Automated Reasoning, Springer Verlag, A Para{\^i}tre

We describe the formalisation in Coq of a proof that the numbers e and $\pi$ are transcendental. This proof lies at the interface of two domains of mathematics that are often considered separately: calculus (real and elementary complex analysis) and algebra. For the work on calculus, we rely on the Coquelicot library and for the work on algebra, we rely on the Mathematical Components library. Moreover, some of the elements of our formalized proof originate in the more ancient library for real numbers included in the Coq distribution. The case of $\pi$ relies extensively on properties of multivariate polynomials and this experiment was also an occasion to put to test a newly developed library for these multivariate polynomials., Comment: in Jeremy Avigad and Adam Chlipala. Certified Programs and Proofs, Jan 2016, St Petersburg, Florida, United States. ACM Press, pp.12, 2016

This article presents the formal proof of correctness for a plane Delaunay triangulation algorithm. It consists in repeating a sequence of edge flippings from an initial triangulation until the Delaunay property is achieved. To describe triangulations, we rely on a combinatorial hypermap specification framework we have been developing for years. We embed hypermaps in the plane by attaching coordinates to elements in a consistent way. We then describe what are legal and illegal Delaunay edges and a flipping operation which we show preserves hypermap, triangulation, and embedding invariants. To prove the termination of the algorithm, we use a generic approach expressing that any non-cyclic relation is well-founded when working on a finite set.

We propose a (limited) solution to the problem of constructing stream values defined by recursive equations that do not respect the guardedness condition. The guardedness condition is imposed on definitions of corecursive functions in Coq, AGDA, and other higher-order proof assistants. In this paper, we concentrate in particular on those non-guarded equations where recursive calls appear under functions. We use a correspondence between streams and functions over natural numbers to show that some classes of non-guarded definitions can be modelled through the encoding as structural recursive functions. In practice, this work extends the class of stream values that can be defined in a constructive type theory-based theorem prover with inductive and coinductive types, structural recursion and guarded corecursion

This study examines the role of external funding in the development of public library network resources and services, their identification, and their benefit and impact, particularly as they affect the digital divide. The study was conducted between February 2001 and January 2002, employing a range of data collection techniques, including site visits, focus groups, surveys analysis of E-rate data sources, local library and state library reports, documents from external funders, and other material. Key findings and issues include: (1) LSTA (Library Services and Technology Act) is a model federal program for funding libraries; (2) E-rate funding is essential to local operations, but needs fine-tuning; (3) leveraging external support to serve those impacted by the digital divide; (4) equipment was not enough; (5) coordination was necessary and the State Library delivered; (6) someone must have authority and responsibility for seeking external funds; (7) remembering the poorest counties and communities; (8) maintaining sustainability; and (9) understanding situational factors. Conclusions, next steps, and recommendations are presented. Appendices include LSTA state plan requirements and assurances, SLD (Schools and Libraries Division) analysis method and description of tables, site visit participants, selected study instruments, and advisory committee members. (Contains 75 references.) (MES)

interpreters are tools to compute approximations for behaviors of a program. These approximations can then be used for optimisation or for error detection. In this paper, we show how to describe an abstract interpreter using the type-theory based theorem prover Coq, using inductive types for syntax and structural recursive programming for the abstract interpreter's kernel. The abstract interpreter can then be proved correct with respect to a Hoare logic for the programming language.

In Constructive Type Theory, recursive and corecursive definitions are subject to syntactic restrictions which guarantee termination for recursive functions and productivity for corecursive functions. However, many terminating and productive functions do not pass the syntactic tests. Bove proposed in her thesis an elegant reformulation of the method of accessibility predicates that widens the range of terminative recursive functions formalisable in Constructive Type Theory. In this paper, we pursue the same goal for productive corecursive functions. Notably, our method of formalisation of coinductive definitions of productive functions in Coq requires not only the use of ad-hoc predicates, but also a systematic algorithm that separates the inductive and coinductive parts of functions., Comment: Dans Coalgebraic Methods in Computer Science (2008)

We describe several views of the semantics of a simple programming language as formal documents in the calculus of inductive constructions that can be verified by the Coq proof system. Covered aspects are natural semantics, denotational semantics, axiomatic semantics, and abstract interpretation. Descriptions as recursive functions are also provided whenever suitable, thus yielding a a verification condition generator and a static analyser that can be run inside the theorem prover for use in reflective proofs. Extraction of an interpreter from the denotational semantics is also described. All different aspects are formally proved sound with respect to the natural semantics specification., Comment: Propos\'e pour publication dans l'ouvrage \`a la m\'emoire de Gilles Kahn

This report summarizes the findings, issues, and lessons learned from the Developing National Public Library and Statewide Network Statistics and Performance Measures study conducted between January 1999 and August 2000. The overall goal of the study was to develop a core set of national statistics and performance measures that librarians, researchers, and policymakers can use to describe public library and library-based statewide network use of networked services and resources. Study participants identified a number of criteria for the selection, development, and collection of network statistics and performance measures. Based on these criteria, and through extensive field-testing using a number of methods, the study team developed a core set of network statistics and performance measures. Key findings, issues, and recommendations include: (1) a core set of national network statistics and performance measures is possible; (2) a number of models exist to determine which statistics to use under what circumstances; (3) network statistics are evolutionary; (4) understanding, using, and presenting network statistics and measures requires education; (5) vendor community collaboration is key; and (6) developing a national data collection system to move forward is critical. (MES)

This study, sponsored by the U.S. National Commission on Libraries and Information Science, sought to: (1) provide longitudinal data regarding the percentage of public libraries connected to the Internet; (2) provide longitudinal data regarding the percentage of public libraries that provide graphical public access Internet services; (3) provide longitudinal data regarding the speed of library public access Internet services; (4) explore the funding sources that support public library Internet connectivity and information technology infrastructure development; (5) explore the level of use of online database resources, blocking technologies, and special software/hardware for individuals with disabilities by public libraries that provide public Internet access service; (6) explore the extent and nature of library public access Internet acceptable use policies; and (7) explore the extent and nature of library Internet training services offered by libraries to various types of library users and staff. Data were collected by a survey mailed to a sample of 1,500 public library outlets in May 2000. This report summarizes key findings by metropolitan status and poverty level. Data tables and the survey form are appended. (MES)

This report provides preliminary findings and a summary of study activities for Stage I of a project that examined public library Internet services that could impact the Digital Divide. The first section discusses the E-rate program and the Digital Divide, including closing the gap in the Digital Divide and public library Internet connectivity and the Digital Divide. Stage I tasks and objectives are presented in the second section, including assessing various data sources that describe the public library's role and impacts on the Digital Divide and conducting preliminary site-based data collection at selected state libraries, public libraries, and consortia. The third section assesses databases as per their usefulness in describing public library Internet services and their impact on the Digital Divide. Data collection at selected state libraries and public libraries is described in the fourth section, including objectives, selecting the states, key findings, importance of leveraged funding, impacts and benefits, issues and barriers, and possible models. The final section considers the next steps for the project. Appendices include a report on available data from the Schools and Libraries Division and the Gates Technology Inventory, a chart of research questions and study areas, and preliminary impact models of public library Internet and technology infrastructure funding. (MES)

We propose to use Tarski's least fixpoint theorem as a basis to define recursive functions in the calculus of inductive constructions. This widens the class of functions that can be modeled in type-theory based theorem proving tool to potentially non-terminating functions. This is only possible if we extend the logical framework by adding the axioms that correspond to classical logic. We claim that the extended framework makes it possible to reason about terminating and non-terminating computations and we show that common facilities of the calculus of inductive construction, like program extraction can be extended to also handle the new functions.

We describe the basic notions of co-induction as they are available in the coq system. As an application, we describe arithmetic properties for simple representations of real numbers.

These notes provide a quick introduction to the Coq system and show how it can be used to define logical concepts and functions and reason about them. It is designed as a tutorial, so that readers can quickly start their own experiments, learning only a few of the capabilities of the system. A much more comprehensive study is provided in [1], which also provides an extensive collection of exercises to train on.

We extend the work of A. Ciaffaglione and P. Di Gianantonio on mechanical verification of algorithms for exact computation on real numbers, using infinite streams of digits implemented as co-inductive types. Four aspects are studied: the first aspect concerns the proof that digit streams can be related to the axiomatized real numbers that are already axiomatized in the proof system (axiomatized, but with no fixed representation). The second aspect re-visits the definition of an addition function, looking at techniques to let the proof search mechanism perform the effective construction of an algorithm that is correct by construction. The third aspect concerns the definition of a function to compute affine formulas with positive rational coefficients. This should be understood as a testbed to describe a technique to combine co-recursion and recursion to obtain a model for an algorithm that appears at first sight to be outside the expressive power allowed by the proof system. The fourth aspect concerns the definition of a function to compute series, with an application on the series that is used to compute Euler's number e. All these experiments should be reproducible in any proof system that supports co-inductive types, co-recursion and general forms of terminating recursion, but we performed with the Coq system [12, 3, 14].

In less than five years, the California State Library-sponsored InFoPeople project connected 46% of California's public libraries to the Internet and established a highly regarded, sustained training program to assist librarians in taking advantage of the new networked resources and services. The primary objective of this Stage II report was to conduct site visits at selected InFoPeople public libraries in the various regional planning areas throughout the state. Findings from the site visits and interviews that are presented in this report cover the following areas: public access to the Internet at public libraries throughout the state; impact of InFoPeople training; utility of the community plan requirement; utility of the community partner requirement; key impacts on library users and communities; key impacts on library operations and services; impact of InFoPeople's "Librarian's Index to the Internet"; future high impact information technology applications for public libraries; next steps for leveling the public library information technology playing field; and InFoPeople operations and services. Issues and recommendations for future InFoPeople directions are also presented. Appendices include the schedule of onsite evaluation interviews, profiles of libraries visited, the letter scheduling onsite visit and requesting information, and a profile of InFoPeople. (AEF)

The purpose of the California State Library-sponsored project, InFoPeople, is to enhance access to information resources by providing points of public access to the Internet in public libraries throughout the state of California. This Stage 1 report represents an initial set of findings and issues related to the InFoPeople project and provides the current status of the evaluation project to date. Specifically, the report presents findings regarding: the reformatting of the quarterly and user surveys, including the development of scripts to migrate data from these surveys into analytical tools such as Excel; an analysis of data contained in these two surveys with a discussion of issues affecting how such data might be better collected, managed, and analyzed in the future; and results of surveys administered to InFoPeople site contacts and community partners. Thirty-four figures and tables present data. Appendices include copies of programming scripts, an outline of changes to the quarterly statistics database, and the library liaison and community partners survey questionnaires. (AEF)

The purpose of this study is to identify users of Pennsylvania public libraries and determine their reasons for using the library. In addition, the study provides information describing the impacts and benefits to those users as a result of their contact with the public library. The objectives were to: (1) describe users in terms of their education, age, sex, and household income; (2) determine the reasons for the use of the public library; (3) understand how use of the public library is valuable or beneficial to these users; and (4) describe the role of Pennsylvania public libraries in supporting economic development at both the local and statewide level. A statewide survey of public library users, site visits to 10 libraries throughout the state, and logs of critical incidents of significant impacts provided data. The study found that there are numerous and important impacts and benefits that result from use of Pennsylvania public libraries. Appendices include: Focus Group interviews "Research Method"; "Focus Group Questions"; a participant questionnaire for library personnel and users; "Critical Impact Log Method"; a public services impact log; "Content Analysis Categories Reference Desk Critical Incident Log"; "Pennsylvania Public Library User Survey"; and survey instructions. (AEF)

This study collected Victorian (Australia) public library and public library user Internet connectivity data that: provides a baseline measure of public library Internet connectivity; describes public library type and level of Internet connectivity; details public library branch Internet connectivity; reviews the costs of public library Internet connectivity; and assesses public library Internet connectivity from the perspective of librarians and users. The study describes the extent and nature of Victorian public library Internet connectivity as of August 1997. The study also describes user-based feedback on public library Internet-based services. Surveys were completed by all 42 Victorian public libraries, and user surveys were completed by 444 users. As of August 1997, 90.5% of Victorian public library services had some type of Internet connection. Overall, 58.5% of public library branches were connected to the Internet. The user survey served to: describe the types of users making use of public library public access Internet services; explore the types of Internet-related activities in which users engaged through the libraries' public access services; and measure the overall satisfaction of users with the libraries' public access services. The report also compares findings from the study with a similar survey of U.S. public library connectivity, highlighting key issues. The library service survey and user survey are appended. (Contains 20 references.) (SWC)

The purpose of this study was to obtain descriptive information about the nation's public library connectivity, use, and costs related to the Internet. The study gathered data from a national sample of public libraries from the period between May and July 1997. Unlike the 1994 and 1996 students, the 1997 study drew a new library sample that differed in 3 significant ways: (1) is used a larger sample size; (3) it did not use the region strata, but rather a metropolitan status strata; and (3) it used redefined population of legal service area strata. The findings presented suggest that there are numerous strategies and approaches for providing Internet-based services and resources to the public; there are numerous models for designing and deploying information technologies to provide access and services; there are multiple approaches and a range of different costs associated with providing these services that depend on local, situational factors that are very difficult to generalize; and that the diversity of public library Internet connectivity configurations, services and costs will continue to increase as libraries strive to provide network-based services in a rapidly evolving policy and technology context. The study limited its attention to the following key areas: budget spent on Internet-related services, technology deployment, and social issues. The data reported contribute to the ongoing effort to address these issues and topics for the public library community as well as for a range of policy makers at the federal, state and local settings. (AEF)

This report discusses selected issues regarding public library Internet connectivity, costs, and use. It discusses the implications of the "1997 Public Libraries and the Internet" study and presents policy recommendations related to the study's findings. This report suggests the importance of federal policy and library management in considering issues beyond simply connecting to the Internet. Questions about the unequal distribution of Internet connectivity, costs and provision of service across library population of legal service areas are raised. The 1997 Study used sample data from "Public Libraries in the United States: 1994," an annual public library data collection collaboration between the National Center for Education Statistics (NCES), National Commission on Libraries and Information Science (NCLIS), and state library agencies. The report examines 10 Federal Information Policies: "Reaching 100% Public Library Connectivity"; "Importance of Internet-Based Services Rather than Connectivity"; "Universal Service"; "Subsidizing Public Library Connection Costs"; "Public Access to Electronic Government Information"; "Effectiveness of the Library Services and Technology Act for Public Libraries"; "Complexity of Internet-Related Costs"; "Need for a New National Data Collection Paradigm"; "Role of the Federal Government"; and "Multiple Federal Public Library Policies and Programs". In addition, nine Public Library Policy Issues are discussed: "Thinking Locally in a Global Networked Environment"; "The Endless Upgrade"; "Focus on Network-Based Services";"Identifying, Describing, and Defining Internet-Related Costs"; "Redeploying Library Resources"; "Comprehensive Internet Costs and Statistics Management"; "Performance Measures and Statistics for Networked Services"; "Resource Sharing"; and "New Models for Learning and Applying Internet Skills." (Contains 37 references.) (JAK)

This report provides an evaluation of the Online at PA Libraries project which was initiated in the Fall of 1996 by the Pennsylvania Department of Education's Office of Commonwealth Libraries and the Schuylkill Intermediate Unit. The report documents that the following goals were accomplished: (1) provide public access to the Internet through Pennsylvania's public libraries; (2) provide library users with timely information for educational research, economic development, and recreational purposes; and (3) ensure that trained library staff are available to help the public find the information they need in an online environment. Key assessment questions were answered by the use of a range of data collection techniques including surveys of librarians and users, site visits, focus groups, interviews, and other techniques. From the viewpoint of project participants, the project was clearly successful. The list of various benefits and impacts that have come to the library, the users, and the community overall is significant and consistent across most libraries. The study concludes with a discussion of key issues raised by the Online at PA Libraries project and lessons that have been learned from this effort that can be incorporated into future efforts. Specific recommendations include building on the project with future projects, developing new roles for Pennsylvania libraries and librarians, and developing a statewide strategic planning effort to continue to take advantage of the evolving global networked environment for the benefit of Pennsylvania residents. The user questionnaire is appended. (Author/AEF)

This compendium is a companion document to the Maryland Sailor Online Public Information Network assessment final report, and contains detailed study findings, study data collection activity write-ups, detailed methodologies, data collection tools, and consultant notes on the uses of the study's data collection instruments. The purpose of the assessment of Maryland's statewide computer network was to: (1) evaluate the value of the Sailor network to such target communities as the public library, K-12, business, minority, and state and local government communities; (2) recommend refinements and modifications to the Sailor network to meet the needs of the target communities; (3) measure the nature and extent of target community use of the Sailor network; and (4) create measurement devices that the Division of Library Development and Services (DLDS) can use in the future to assess the Sailor network. Data collection activities included: case studies of the five Maryland library systems, including focus groups and interviews with site personnel; mail and quick response surveys; focus groups and interviews with key Sailor entities; preliminary study result presentations; Sailor network traffic data collection; Sailor Web page assessment in comparison to five other statewide state library-run network Web pages; content analysis of case site, DLDS, and Sailor Operations Sailor-related planning, training, and manual documentation; and pre-testing data collection instruments, continual consultation with, and presentations to the Sailor network assessment Advisory Committee, DLDS, and the Maryland Library Association. Appendices include a cover letter and survey of school library media specialist internet use. (Author/SWC)

This report describes the results of an assessment of Sailor, Maryland's Online Public Information Network, which provides statewide Internet connection to 100% of Maryland public libraries. The concept of a "statewide networked environment" includes information services, products, hardware and software, telecommunications infrastructure, and resources that users and providers of the statewide network receive via the network. The statewide networked environment comprises both state networks and locally developed information services, and serves as a gateway to national and international information services. The purpose of the assessment was to: (1) evaluate the value of the Sailor network to such target communities as the public library, K-12, business, minority, and state and local government communities; (2) recommend refinements and modifications to the Sailor network to meet the needs of the target communities; (3) measure the nature and extent of target community use of the Sailor network; and (4) create measurement devices that the Division of Library Development and Services (DLDS) can use in the future to assess the Sailor network. This report details key findings, future Sailor development models, and provides recommendations. Appendices include: Seymour Plan Vision Statement; Sailor Network Funding Expenditures Summary and Governance Board Membership; The Piper Letter: Making Sense of Web Usage Statistics; and Sailor Operations Center Fiscal Year 1996 Annual Report. (Contains 12 references.) (SWC)

This 1996 National Commission on Libraries and Information Science (NCLIS) survey gathered data from a national sample of public libraries concerning the current level of public library involvement with the Internet. The purpose of this study was to: (1) provide policymakers, researchers, and library professionals with longitudinal data that measured changes in public library Internet involvement since the first survey in 1994; (2) identify costs for public library Internet services; and (3) identify issues and inform the policy debate concerning public library roles in the electronic networked environment. This final report is divided into three sections: Introduction; Study Results; and Progress and Issues. The introduction discusses the Telecommunications Act of 1996 and the Library Services and Construction Act/Library Services and Technology Act; intellectual property and the National Information Infrastructure; and an electronic federal depository library program. The second section discusses study methodology; public library demographics; accessing the Internet; the current state of public library Internet connectivity; Internet uses and public access services; and benefits to connecting to the Internet. The third section focuses on disparities; connectivity versus services; the goal of universal service; quality of network services; the life cycle of public library Internet development; and preparation for the next survey. Appendices include the survey instrument, survey alert, and cover letter, and information about the authors. (Contains 27 references, and 45 figures that present survey data.) (Author/AEF)