1 resultado para Infinite radical
em Boston University Digital Common
Filtro por publicador
- Acceda, el repositorio institucional de la Universidad de Las Palmas de Gran Canaria. España (4)
- AMS Tesi di Dottorato - Alm@DL - Università di Bologna (3)
- AMS Tesi di Laurea - Alm@DL - Università di Bologna (2)
- Andina Digital - Repositorio UASB-Digital - Universidade Andina Simón Bolívar (5)
- ArchiMeD - Elektronische Publikationen der Universität Mainz - Alemanha (9)
- Argos - Repositorio Institucional de la Secretaría de Investigación y Postgrado de la Facultad de Humanidades y Ciencias Sociales de la Universidad Nacional de Misiones (2)
- Avian Conservation and Ecology - Eletronic Cientific Hournal - Écologie et conservation des oiseaux: (1)
- Biblioteca Digital | Sistema Integrado de Documentación | UNCuyo - UNCUYO. UNIVERSIDAD NACIONAL DE CUYO. (3)
- Biblioteca Digital da Produção Intelectual da Universidade de São Paulo (14)
- Biblioteca Digital da Produção Intelectual da Universidade de São Paulo (BDPI/USP) (20)
- Biblioteca Digital de la Universidad Católica Argentina (1)
- Biblioteca Digital de Teses e Dissertações Eletrônicas da UERJ (2)
- Biblioteca Valenciana Digital - Ministerio de Educación, Cultura y Deporte - Valencia - Espanha (5)
- Bibloteca do Senado Federal do Brasil (43)
- BORIS: Bern Open Repository and Information System - Berna - Suiça (139)
- Boston University Digital Common (1)
- Brock University, Canada (3)
- Bucknell University Digital Commons - Pensilvania - USA (17)
- CaltechTHESIS (8)
- Cambridge University Engineering Department Publications Database (48)
- CentAUR: Central Archive University of Reading - UK (49)
- Chinese Academy of Sciences Institutional Repositories Grid Portal (69)
- Cochin University of Science & Technology (CUSAT), India (3)
- Collection Of Biostatistics Research Archive (1)
- CUNY Academic Works (1)
- Dalarna University College Electronic Archive (1)
- Deakin Research Online - Australia (55)
- DI-fusion - The institutional repository of Université Libre de Bruxelles (1)
- Digital Commons - Michigan Tech (3)
- Digital Commons @ DU | University of Denver Research (2)
- Diposit Digital de la UB - Universidade de Barcelona (1)
- Duke University (5)
- FAUBA DIGITAL: Repositorio institucional científico y académico de la Facultad de Agronomia de la Universidad de Buenos Aires (3)
- Gallica, Bibliotheque Numerique - Bibliothèque nationale de France (French National Library) (BnF), France (17)
- Greenwich Academic Literature Archive - UK (2)
- Helda - Digital Repository of University of Helsinki (5)
- Indian Institute of Science - Bangalore - Índia (93)
- Instituto Politécnico do Porto, Portugal (2)
- Massachusetts Institute of Technology (1)
- Memoria Académica - FaHCE, UNLP - Argentina (30)
- Ministerio de Cultura, Spain (10)
- National Center for Biotechnology Information - NCBI (11)
- Plymouth Marine Science Electronic Archive (PlyMSEA) (2)
- Publishing Network for Geoscientific & Environmental Data (1)
- QUB Research Portal - Research Directory and Institutional Repository for Queen's University Belfast (87)
- Queensland University of Technology - ePrints Archive (74)
- Repositório digital da Fundação Getúlio Vargas - FGV (6)
- Repositório Digital da UNIVERSIDADE DA MADEIRA - Portugal (1)
- Repositorio Institucional de la Universidad Nacional Agraria (1)
- Repositório Institucional UNESP - Universidade Estadual Paulista "Julio de Mesquita Filho" (79)
- RUN (Repositório da Universidade Nova de Lisboa) - FCT (Faculdade de Cienecias e Technologia), Universidade Nova de Lisboa (UNL), Portugal (2)
- School of Medicine, Washington University, United States (2)
- Universidad Autónoma de Nuevo León, Mexico (4)
- Universidad de Alicante (2)
- Universidad del Rosario, Colombia (1)
- Universidad Politécnica de Madrid (19)
- Universidade Federal do Pará (6)
- Universidade Federal do Rio Grande do Norte (UFRN) (2)
- Universitat de Girona, Spain (1)
- Universitätsbibliothek Kassel, Universität Kassel, Germany (1)
- Université de Lausanne, Switzerland (1)
- Université de Montréal, Canada (6)
- University of Connecticut - USA (1)
- University of Washington (1)
- WestminsterResearch - UK (3)
Resumo:
We generalize the well-known pebble game to infinite dag's, and we use this generalization to give new and shorter proofs of results in different areas of computer science (as diverse as "logic of programs" and "formal language theory"). Our applications here include a proof of a theorem due to Salomaa, asserting the existence of a context-free language with infinite index, and a proof of a theorem due to Tiuryn and Erimbetov, asserting that unbounded memory increases the power of logics of programs. The original proofs by Salomaa, Tiuryn, and Erimbetov, are fairly technical. The proofs by Tiuryn and Erimbetov also involve advanced techniques of model theory, namely, back-and-forth constructions based on a variant of Ehrenfeucht-Fraisse games. By contrast, our proofs are not only shorter, but also elementary. All we need is essentially finite induction and, in the case of the Tiuryn-Erimbetov result, the compactness and completeness of first-order logic.