1 resultado para correctness verification
em Universitätsbibliothek Kassel, Universität Kassel, Germany
Filtro por publicador
- Aberdeen University (2)
- Acceda, el repositorio institucional de la Universidad de Las Palmas de Gran Canaria. España (1)
- AMS Tesi di Dottorato - Alm@DL - Università di Bologna (6)
- AMS Tesi di Laurea - Alm@DL - Università di Bologna (5)
- Aquatic Commons (13)
- Archive of European Integration (13)
- Archivo Digital para la Docencia y la Investigación - Repositorio Institucional de la Universidad del País Vasco (8)
- Aston University Research Archive (25)
- Biblioteca Digital da Câmara dos Deputados (1)
- Biblioteca Digital da Produção Intelectual da Universidade de São Paulo (4)
- Biblioteca Digital da Produção Intelectual da Universidade de São Paulo (BDPI/USP) (3)
- Biblioteca Digital de la Universidad Católica Argentina (3)
- Biblioteca Digital de Teses e Dissertações Eletrônicas da UERJ (28)
- BORIS: Bern Open Repository and Information System - Berna - Suiça (21)
- Boston University Digital Common (8)
- Brock University, Canada (1)
- Bulgarian Digital Mathematics Library at IMI-BAS (6)
- CaltechTHESIS (7)
- Cambridge University Engineering Department Publications Database (66)
- CentAUR: Central Archive University of Reading - UK (29)
- Chinese Academy of Sciences Institutional Repositories Grid Portal (71)
- Cochin University of Science & Technology (CUSAT), India (3)
- Comissão Econômica para a América Latina e o Caribe (CEPAL) (2)
- Corvinus Research Archive - The institutional repository for the Corvinus University of Budapest (1)
- CUNY Academic Works (1)
- Dalarna University College Electronic Archive (3)
- Deakin Research Online - Australia (30)
- Department of Computer Science E-Repository - King's College London, Strand, London (6)
- Digital Commons - Michigan Tech (1)
- Digital Commons at Florida International University (6)
- Digital Repository at Iowa State University (2)
- DigitalCommons@The Texas Medical Center (7)
- DigitalCommons@University of Nebraska - Lincoln (1)
- Doria (National Library of Finland DSpace Services) - National Library of Finland, Finland (1)
- DRUM (Digital Repository at the University of Maryland) (1)
- Duke University (2)
- Düsseldorfer Dokumenten- und Publikationsservice (1)
- eResearch Archive - Queensland Department of Agriculture; Fisheries and Forestry (7)
- Glasgow Theses Service (2)
- Greenwich Academic Literature Archive - UK (2)
- Helda - Digital Repository of University of Helsinki (21)
- Indian Institute of Science - Bangalore - Índia (105)
- INSTITUTO DE PESQUISAS ENERGÉTICAS E NUCLEARES (IPEN) - Repositório Digital da Produção Técnico Científica - BibliotecaTerezine Arantes Ferra (3)
- Instituto Politécnico do Porto, Portugal (1)
- Massachusetts Institute of Technology (3)
- Memoria Académica - FaHCE, UNLP - Argentina (3)
- National Center for Biotechnology Information - NCBI (2)
- Publishing Network for Geoscientific & Environmental Data (1)
- QUB Research Portal - Research Directory and Institutional Repository for Queen's University Belfast (26)
- Queensland University of Technology - ePrints Archive (286)
- Repositório Alice (Acesso Livre à Informação Científica da Embrapa / Repository Open Access to Scientific Information from Embrapa) (1)
- Repositório Digital da UNIVERSIDADE DA MADEIRA - Portugal (1)
- Repositório Institucional da Universidade Federal do Rio Grande do Norte (2)
- Repositório Institucional UNESP - Universidade Estadual Paulista "Julio de Mesquita Filho" (9)
- School of Medicine, Washington University, United States (2)
- Universidad Politécnica de Madrid (27)
- Universidade Federal do Rio Grande do Norte (UFRN) (6)
- Universitätsbibliothek Kassel, Universität Kassel, Germany (1)
- Université de Montréal (1)
- Université de Montréal, Canada (3)
- University of Michigan (25)
- University of Queensland eSpace - Australia (24)
Resumo:
This paper contributes to the study of Freely Rewriting Restarting Automata (FRR-automata) and Parallel Communicating Grammar Systems (PCGS), which both are useful models in computational linguistics. For PCGSs we study two complexity measures called 'generation complexity' and 'distribution complexity', and we prove that a PCGS Pi, for which the generation complexity and the distribution complexity are both bounded by constants, can be transformed into a freely rewriting restarting automaton of a very restricted form. From this characterization it follows that the language L(Pi) generated by Pi is semi-linear, that its characteristic analysis is of polynomial size, and that this analysis can be computed in polynomial time.