Subject: Theory of computation | Mathematics of computing | Computing methodologies | Computer systems organization | Computer Science - Computational Complexity
The outcomes of this article are twofold.
Implicit complexity. We provide an implicit characterization of polynomial time computation in terms of ordinary differential equations: we characterize the class P of languages computable in polynomial time in terms of diff... View more
Rajeev Alur and David L. Dill. Automata for modeling real-time systems. In Mike Paterson, editor, Automata, Languages and Programming, 17th International Colloquium, ICALP90, Warwick University, England, July 16-20, 1990, Proceedings, volume 443 of Lecture Notes in Computer Science, pages 322-335. Springer, 1990.
A. Ben-Hur, H. T. Siegelmann, and S. Fishman. A theory of complexity for continuous time systems. J. Complexity, 18(1):51-86, 2002.
Asa Ben-Hur, Joshua Feinberg, Shmuel Fishman, and Hava T. Siegelmann. Probabilistic analysis of a differential equation for linear programming. Journal of Complexity, 19(4):474- 510, 2003.
L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and Real Computation. Springer, 1998.
In J.-Y. Cai, S. B. Cooper, and A. Li, editors, Theory and Applications of Models of Computation TAMC'06, LNCS 3959, pages 631-643. Springer-Verlag, 2006.
Complexity, 23(3):317-335, 2007.
Olivier Bournez. Some bounds on the computational power of piecewise constant derivative systems (extended abstract). In ICALP, pages 143-153, 1997.
Theoret. Comput. Sci., 210(1):21-71, 1999.
Olivier Bournez and Manuel L. Campagnolo. New Computational Paradigms. Changing Conceptions of What is Computable, chapter A Survey on Continuous Time Computations, pages 383-423. Springer-Verlag, New York, 2008.
Olivier Bournez, Felipe Cucker, Paulin Jacobé de Naurois, and Jean-Yves Marion. Implicit complexity over an arbitrary structure: Sequential and parallel polynomial time. Journal of Logic and Computation, 15(1):41-58, 2005.