On the computational complexity of Data Flow Analysis
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2013
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909311962185728 |
|---|---|
| author | Sood, Gaurav Krishnan, K. Murali |
| author_facet | Sood, Gaurav Krishnan, K. Murali |
| contents | We consider the problem of Data Flow Analysis over monotone data flow frameworks with a finite lattice. The problem of computing the Maximum Fixed Point (MFP) solution is shown to be P-complete even when the lattice has just four elements. This shows that the problem is unlikely to be efficiently parallelizable. It is also shown that the problem of computing the Meet Over all Paths (MOP) solution is NL-complete (and hence efficiently parallelizable) when the lattice is finite even for non-monotone data flow frameworks. These results appear in contrast with the fact that when the lattice is not finite, solving the MOP problem is undecidable and hence significantly harder than the MFP problem which is polynomial time computable for lattices of finite height. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1303_4315 |
| institution | arXiv |
| publishDate | 2013 |
| record_format | arxiv |
| spellingShingle | On the computational complexity of Data Flow Analysis Sood, Gaurav Krishnan, K. Murali Computational Complexity 68Q17 F.1.3; D.3.4; F.3.2 We consider the problem of Data Flow Analysis over monotone data flow frameworks with a finite lattice. The problem of computing the Maximum Fixed Point (MFP) solution is shown to be P-complete even when the lattice has just four elements. This shows that the problem is unlikely to be efficiently parallelizable. It is also shown that the problem of computing the Meet Over all Paths (MOP) solution is NL-complete (and hence efficiently parallelizable) when the lattice is finite even for non-monotone data flow frameworks. These results appear in contrast with the fact that when the lattice is not finite, solving the MOP problem is undecidable and hence significantly harder than the MFP problem which is polynomial time computable for lattices of finite height. |
| title | On the computational complexity of Data Flow Analysis |
| topic | Computational Complexity 68Q17 F.1.3; D.3.4; F.3.2 |
| url | https://arxiv.org/abs/1303.4315 |