1 resultado para Infinite delay
em Boston University Digital Common
Filtro por publicador
- Aberdeen University (2)
- AMS Tesi di Laurea - Alm@DL - Università di Bologna (1)
- ArchiMeD - Elektronische Publikationen der Universität Mainz - Alemanha (4)
- Archive of European Integration (5)
- Archivo Digital para la Docencia y la Investigación - Repositorio Institucional de la Universidad del País Vasco (5)
- Aston University Research Archive (51)
- Biblioteca Digital da Produção Intelectual da Universidade de São Paulo (16)
- Biblioteca Digital da Produção Intelectual da Universidade de São Paulo (BDPI/USP) (10)
- BORIS: Bern Open Repository and Information System - Berna - Suiça (29)
- Boston University Digital Common (1)
- Brock University, Canada (3)
- Bucknell University Digital Commons - Pensilvania - USA (1)
- Bulgarian Digital Mathematics Library at IMI-BAS (9)
- CaltechTHESIS (6)
- Cambridge University Engineering Department Publications Database (78)
- CentAUR: Central Archive University of Reading - UK (49)
- Centro Hospitalar do Porto (1)
- Chinese Academy of Sciences Institutional Repositories Grid Portal (37)
- Cochin University of Science & Technology (CUSAT), India (8)
- Coffee Science - Universidade Federal de Lavras (1)
- Collection Of Biostatistics Research Archive (1)
- CORA - Cork Open Research Archive - University College Cork - Ireland (3)
- Corvinus Research Archive - The institutional repository for the Corvinus University of Budapest (1)
- CUNY Academic Works (1)
- Dalarna University College Electronic Archive (1)
- Deakin Research Online - Australia (112)
- Digital Commons at Florida International University (10)
- Digital Peer Publishing (2)
- DigitalCommons@The Texas Medical Center (2)
- DigitalCommons@University of Nebraska - Lincoln (1)
- Diposit Digital de la UB - Universidade de Barcelona (1)
- DRUM (Digital Repository at the University of Maryland) (1)
- Duke University (5)
- eResearch Archive - Queensland Department of Agriculture; Fisheries and Forestry (1)
- FUNDAJ - Fundação Joaquim Nabuco (1)
- Greenwich Academic Literature Archive - UK (1)
- Helda - Digital Repository of University of Helsinki (2)
- Helvia: Repositorio Institucional de la Universidad de Córdoba (1)
- Illinois Digital Environment for Access to Learning and Scholarship Repository (1)
- Indian Institute of Science - Bangalore - Índia (132)
- Instituto Politécnico de Bragança (2)
- Instituto Politécnico do Porto, Portugal (3)
- Instituto Superior de Psicologia Aplicada - Lisboa (1)
- Lume - Repositório Digital da Universidade Federal do Rio Grande do Sul (1)
- Massachusetts Institute of Technology (1)
- Ministerio de Cultura, Spain (1)
- National Center for Biotechnology Information - NCBI (7)
- Nottingham eTheses (2)
- Plymouth Marine Science Electronic Archive (PlyMSEA) (3)
- Publishing Network for Geoscientific & Environmental Data (1)
- QUB Research Portal - Research Directory and Institutional Repository for Queen's University Belfast (59)
- Queensland University of Technology - ePrints Archive (52)
- RCAAP - Repositório Científico de Acesso Aberto de Portugal (1)
- Repositório Aberto da Universidade Aberta de Portugal (1)
- Repositório Alice (Acesso Livre à Informação Científica da Embrapa / Repository Open Access to Scientific Information from Embrapa) (1)
- Repositório Científico da Universidade de Évora - Portugal (1)
- Repositório digital da Fundação Getúlio Vargas - FGV (3)
- Repositório Institucional da Universidade de Aveiro - Portugal (1)
- Repositorio Institucional de la Universidad Pública de Navarra - Espanha (1)
- Repositório Institucional UNESP - Universidade Estadual Paulista "Julio de Mesquita Filho" (39)
- School of Medicine, Washington University, United States (3)
- South Carolina State Documents Depository (1)
- Universidad de Alicante (17)
- Universidad Politécnica de Madrid (26)
- Universidade Estadual Paulista "Júlio de Mesquita Filho" (UNESP) (2)
- Universitat de Girona, Spain (2)
- Universitätsbibliothek Kassel, Universität Kassel, Germany (2)
- Université de Lausanne, Switzerland (2)
- Université de Montréal, Canada (3)
- University of Connecticut - USA (1)
- University of Michigan (46)
- University of Queensland eSpace - Australia (15)
- University of Washington (1)
- WestminsterResearch - UK (11)
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.