Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.1/1035
Título: Robust computations with dynamical systems
Autor: Bournez, Olivier
Graça, Daniel
Hainry, Emmanuel
Palavras-chave: Veri cation
Analog computations
Computable analysis
Model-checking
Data: 2010
Editora: P. Hlinený and A. Kucera
Relatório da Série N.º: Lecture Notes in Computer Science ARCoSS (Advanced Research in Computing and Software Science);6281
Resumo: In this paper we discuss the computational power of Lipschitz dynamical systems which are robust to in nitesimal perturbations. Whereas the study in [1] was done only for not-so-natural systems from a classical mathematical point of view (discontinuous di erential equation systems, discontinuous piecewise a ne maps, or perturbed Turing machines), we prove that the results presented there can be generalized to Lipschitz and computable dynamical systems. In other words, we prove that the perturbed reachability problem (i.e. the reachability problem for systems which are subjected to in nitesimal perturbations) is co-recursively enumerable for this kind of systems. Using this result we show that if robustness to in nitesimal perturbations is also required, the reachability problem becomes decidable. This result can be interpreted in the following manner: undecidability of veri cation doesn't hold for Lipschitz, computable and robust systems. We also show that the perturbed reachability problem is co-r.e. complete even for C1-systems.
Peer review: yes
URI: http://hdl.handle.net/10400.1/1035
Versão do Editor: http://www.springerlink.com/content/pux2120952u4207t/
Aparece nas colecções:FCT2-Artigos (em revistas ou actas indexadas)

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
10-BGH-robust.pdf193,86 kBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.