José Félix Costa (Theoretical Computer Science)
Associate Professor
( Logic and Computation, Department of Mathematics, IST Technical University of Lisbon. )
( Member of CMAF Centro de Matemática e Aplicações Fundamentais, Associate Member of CFCUL Centro de Filosofia das Ciências da Universidade de Lisboa. )
Tityrus
O Meliboee, deus nobis haec otia fecit;
namque erit ille mihi semper deus; illius aram
saepe tener nostris ab ouilibus imbuet agnus.
Ille meas errare boues, ut cernis, et ipsum
ludere quae uellem calamo permisit agresti.
(P. Vergili Maronis, Bucolica I)
Profile
- Research interests:
Algorithmic scientific inference;
physics and computation;
structural complexity;
theory of measurement (as branch of mathematical logic);
foundations of physics;
computability and complexity in digital and analog computational systems;
non-standard models of computation.
- Other interests:
History and philosophy of science; science and art; cosmology.
- Further interests:
Ancient egyptian; teology.
- I have the BSc and MSc in Physics, the MSc in Applied Mathematics, the PhD in Mathematics, and the Aggregation (Habilitation) in Computer Science.
- I got a (portuguese) Descartes award (1992), together with Amílcar and Cristina Sernadas, and a (portuguese) IBM honourable mention (1992).
- I lectured in a broad range of disciplines:
Computability and Complexity,
Algebraic Methods in Computer Science,
History of Science, and
Mathematical Physics.
- Hobbies: ... essentially Tintinolatrie
Special forthcoming events
- Turing Centenary CiE 2012 Conference: POSTER.
- Program Commitee member of the International Workshop on Theoretical Computer Science Dedicated to Professor Cristian S. Calude's 60th Birthday, Auckland, New Zealand, 21--24 Feb 2012.
- Invited speaker of the Workshop The Incomputable, Kavli Royal Society International Centre, Chicheley Hall, 12--15 June, 2012.
- Invited speaker of the Workshop Physics and Computation, Institut Henri Poincaré, 28-30 June, 2012.
- Program Commitee member of the Conference Unconventional Computation & Natural Computing 2012, LIFO, University of Orléans (France), 3--7 September, 2012.
Editorial board
- Review. The Extended Analog Computer and Functions Computable in a Digital Sense by Monika Piekarz, Acta Cybernetica 19: 749-764, 2010.
- Review. Descriptional Complexity of Splicing Systems, by Remco Loos, Andreas Malcher, and Detlef Wotschke, International Journal of Foundations of Computer Science 19(4): 813 -- 826, World Scientific Publishing Company, 2008.
- Review. Super-recursive Algorithms, by Mark Burgin, Springer, 2005.
- Review. The computational complexity of one-dimensional sandpiles, by Peter Bro Miltersen, Theory of Computing Systems 41: 119--125, Springer, 2007.
- Review. Low complexity classes of multidimensional cellular automata, by Véronique Terrier, Theoretical Computer Science 69: 142--156, Elsevier, 2006.
- Review. Membrane computing and complexity theory: a characterization of PSPACE, by Petr Sosík and Alfonso Rodríguez-Páton, J. Comput. Systems Sci. 73: 137--152, Elsevier, 2007.
- Review. Three simulations of Turing machines with the use of real recursive functions, by Monika Piekarz, Ann. Univ. Mariae Curie-Skłodowska Sect. AI Inform. 2, 101--114, 2004.
Book review
Selected articles
- Editorial Physics and Computation, by Cris Calude, José Félix Costa, and Hélia Guerra, Towards a Computational Interpretation of Physical Theories, Applied Mathematics and Computation, to appear.
- Axiomatising physical experiments as oracles to algorithms, by Edwin Beggs, José Félix Costa, and John V. Tucker, 2011, 30 pp, submitted.
- The ARNN model relativises P == NP and P =/= NP, by José Félix Costa and Raimundo Leong, 2011, 44 pp, submitted.
- The impact of models of a physical oracle on computational power, by Edwin Beggs, José Félix Costa, and John V. Tucker. Mathematical Structures in Computer Science, Cambridge University Press, 2011, 27 pp, to appear.
- Unifying science through computation: Reflections on computability and physics, by Edwin Beggs, José Félix Costa, and John V. Tucker. Olga Pombo, Juan Manuel Torres, John Symons, and S. Rahman (editors): Special Sciences and the Unity of Science, Book series: Logic, Epistemology, and the Unity of Science, Vol. 24, Springer, February 2012, to appear.
- Comparing complexity classes relative to physical oracles (short version), by Edwin Beggs, José Félix Costa, and John V. Tucker. Fernando Ferreira, Hélia Guerra, Elvira Mayordomo, and João Rasga (editors), Programs, Proofs, Processes, 6th Conference on Computability in Europe, CiE 2010, Ponta Delgada, Azores, Portugal, June/July 2010, CMATI (Centre for Applied Mathematics and Information Technology), University of Azores, 2010, 62--72.
- Limits to measurements in experiments governed by algorithms, by Edwin Beggs, José Félix Costa, and John V. Tucker. Salvador Elías Venegas-Andraca (editor): Physics and computer science – quantum computation and other approaches, Mathematical Structures in Computer Science 20(06): 1019--1050, Cambridge University Press, 2010.
- Computable scientists, uncomputable world, by José Félix Costa. Cristian S. Calude, Masami Hagiya, Kenichi Morita, Grzegorz Rozenberg, and Jon Timmis (Editors), Unconventional Computation 2010, Tokyo, June 21--25, Lecture Notes in Computer Science 6079: 6--10:, Springer-Verlag, 2010.
- Physical oracles: the Turing machine and the Wheatstone bridge, by Edwin Beggs, José Félix Costa, and John V. Tucker. Diederik Aerts, Sonja Smets, and Jean Paul Van Bendegeme (editors): The Contributions of Logic to the Foundations of Physics, Studia Logica, 95(1--2): 279--300, July 2010.
- Computational Models of Measurement and Hempel's Axiomatization, by Edwin Beggs, José Félix Costa, and John V. Tucker. Book Chapter, in Arturo Carsetti (editor): Causality, Meaningful Complexity and Embodied Cognition, Series: Theory and Decision Library A, Vol. 46: 155--184, Springer, 2010. Article.
- A foundation for real recursive function theory, by José Félix Costa, Bruno Loff, and Jerzy Mycka. Samuel R. Buss, S. Barry Cooper, Benedikt Löwe, and Andrea Sorbi, Computation and Logic in the Real World: CiE 2007, Annals of Pure and Applied Logic, 160(3): 255--288, 2009.
- Computational complexity with experiments as oracles. II. Upper bounds, by Edwin Beggs, José Félix Costa, Bruno Loff, and John V. Tucker. Proceedings of the Royal Society, Series A (Mathematical, Physical and Engineering Sciences), 465(2105): 1453--1465, 2009.
- Processes with local and global liveness requirements, by Hélia Guerra and José Félix Costa. The Journal of Logic and Algebraic Programming, 78(3): 117--137, 2009.
- Physical experiments as oracles, by Edwin Beggs, José Félix Costa, and John V. Tucker. Bulletin of the European Association for Theoretical Computer Science 97:137--151, February 2009.
- Five views of hypercomputation, by Bruno Loff and José Félix Costa. Mike Stannett (editor): Future Trends in Hypercomputation, International Journal of Unconventional Computing, 5(3--4): 193--207, Old City Publishing, Inc., 2009.
- Oracles and advice as measurements, by Edwin Beggs, José Félix Costa, Bruno Loff, and John V. Tucker. Cristian S. Calude et al. (editors), Unconventional Computation 2008, UC ' 08, Vienna, August 25--28, Lecture Notes in Computer Science 5204: 33--50, Springer, 2008.
- Computational complexity with experiments as oracles, by Edwin Beggs, José Félix Costa, Bruno Loff, and John V. Tucker. Proceedings of the Royal Society, Series A (Mathematical, Physical and Engineering Sciences), 464: 2777--2801, October 8, 2008.
- On the complexity of measurement in classical physics, by Edwin Beggs, José Félix Costa, Bruno Loff, and John V. Tucker. M. Agrawal, D. Du, Z. Duan, and A. Li (editors), Theory and Applications of Models of Computation, TAMC 2008, Xi'an, China, April 25--29, 2008, Lecture Notes in Computer Science 4978: 20--30, Springer, 2008.
- The Euclid abstract machine, by Jerzy Mycka, José Félix Costa, and Francisco Coelho. Andrew Adamatzky and Susan Stepney (editors): Towards Theory of Unconventional Computing, International Journal of Unconventional Computing, 4(3): 223--248, Old City Publishing, Inc., 2008.
- Computability on reals, infinite limits and differential equations, by Bruno Loff, José Félix Costa, and Jerzy Mycka. Applied Mathematics and Computation, 191(2): 353--371, Elsevier, 2007.
- A new conceptual framework for analog computation, by Jerzy Mycka and José Félix Costa. Theoretical Computer Science, 374(1--3): 277--290, Elsevier, 2007.
- Undecidability over continuous-time, by Jerzy Mycka and José Félix Costa. Arnon Avron, Nachum Dershowitz, and Alexander Rabinovich (editors): Logics and Models of Computation: An International Logic and Computer Science Semester at Tel Aviv, Logic Journal of the IGPL, 14(5): 649--658, Oxford University Press, 2006.
- Real recursive functions and their hierarchy, by Jerzy Mycka and José Félix Costa. Journal of Complexity, 20(6): 835--857, Elsevier, 2005.
- The computational power of continuous dynamic systems, by Jerzy Mycka and José Félix Costa. in Maurice Margenstern (editor), Machines, Computations, and Universality, MCU 2004, Lecture Notes in Computer Science, 3354: 164--175, Springer-Verlag, 2004.
- Analog computers and recursive functions over the reals, by Daniel Graça and José Félix Costa. Journal of Complexity, 19(5): 644--664, 2003.
- An analog characterization of the Grzegorczyk hierarchy, by Manuel Campagnolo, Cris Moore, and José Félix Costa. Journal of Complexity, 18(4): 977--1000, 2002.
- Canonical institutions of behaviour, by José Félix Costa and Hugo Lourenço. Maura Cerioli and Gianna Reggio (eds.), Lecture Notes in Computer Science, 2267: 71--84, Springer-Verlag, 2001.
- Iteration, inequalities, and differentiability in analog computers, by Manuel Campagnolo, Cris Moore, and José Félix Costa. Journal of Complexity, 16(4): 642--660, 2000.
- Nonsequential automata semantics for a concurrent object-based language, by Paulo B. Meneses, Amílcar Sernadas, and José Félix Costa, Electronic Notes in Theoretical Computer Science, 14(1): 245--273, 1998.
- Mirror, mirror in my hand... a duality between specifications and models of process behaviour, by José Luiz Fiadeiro and José Félix Costa. Mathematical Structures in Computer Science, 6(4): 353--373, 1996.
- Synchronization in Petri nets, by Paulo B. Meneses and José Félix Costa. Fudamenta Informaticae, 26: 11--22, 1996.
- Object specification logic, by Amílcar Sernadas, Cristina Sernadas, and José Félix Costa. Journal of Logic and Computation, 5(5): 603--630, 1995.
- Institutions for behaviour specification, by José Luiz Fiadeiro and José Félix Costa. E. Astesiano, G. Reggio, and A. Tarlecki (eds), Recent Trends in Data Type Specification: 10th Workshop on Specification of Abstract Data Types -- Selected Papers, Lecture Notes in Computer Science, 906: 273--289, Springer-Verlag, 1995.
- Compositional reification of concurrent systems, by Paulo B. Meneses and José Félix Costa. Journal of the Brazilian Computer Society, 2(1): 50--67, 1995.
- Progress assumption in concurrent systems, by José Félix Costa and Amílcar Sernadas. Formal Aspects of Computing, 7(1): 18--36, 1995.
- Object inheritance beyond subtyping, by José Félix Costa, Amílcar Sernadas, and Cristina Sernadas. Acta Informatica, 31(1): 5--26, 1994.
- An institution of object behaviour, by Amílcar Sernadas, José Félix Costa, and Cristina Sernadas. H. Ehrig and F. Orejas (eds), Recent Trends in Data Type Specification: 9th Workshop on Specification of Abstract Data Types -- Selected Papers, Lecture Notes in Computer Science, 785: 337--350, Springer-Verlag, 1994.
- Data encapsulation and modularity: Three views of inheritance, by José Félix Costa, Amílcar Sernadas, and Cristina Sernadas. A. Borzyszkowski and S. Sokolowski (eds), Mathematical Foundations of Computer Science 93, Lecture Notes in Computer Science, 711: 382--391. Springer-Verlag, 1993.
- Process semantics of temporal logic specification, by José Luiz Fiadeiro, José Félix Costa, Amílcar Sernadas, and Tom Maibaum. M. Bidoit and C. Choppy (eds), Recent Trends in Data Type Specification: 8th Workshop on Specification of Abstract Data Types -- Selected Papers, Lecture Notes in Computer Science, 655: 236--253, Springer-Verlag, 1993.
- Object interaction, by José Félix Costa, Amílcar Sernadas, Cristina Sernadas, and Hans-Dieter Ehrich. I. Havel and V. Koubek (eds), Mathematical Foundations of Computer Science 92, Lecture Notes in Computer Science, 629: 200--208, Springer-Verlag, 1992.
Database
- My publications in MathSciNet. Other publications can be found in the DBLP database. Link to Web of Science, Thomson Reuters.
Edition
- Cristian S. Calude, José Félix Costa, and Hélia Guerra, (guest) editors of a Special Issue of Applied Mathematics and Computation, Elsevier, «Towards a computational interpretation of physical theories», to appear.
- Cristian S. Calude and José Félix Costa, (guest) editors of a Special Issue of International Journal of Unconventional Computing, 7(5), September/October 2011, Old City Publishing Science Journals, Special Issue on Physics and Computation (P&C 2010), online.
- José Félix Costa and Nachum Dershowitz, (guest) editors of a Special Issue of Natural Computing, Springer, on Unconventional Computation (UC 2009), 10(4), December 2011, online.
- Cristian S. Calude and José Félix Costa, (guest) editors of a Special Issue of Natural Computing 9(4), December 2010, Springer, on Unconventional Computation (UC 2008), online.
- Cristian S. Calude, José Félix Costa, Nachum Dershowitz, Elisabete Freire, and Grzegorz Rozenberg editors of Lecture Notes in Computer Science, volume 5715, Unconventional Computation 8th International Conference, UC 2009, Ponta Delgada, Azores, Portugal, September 7--11, 2009, Proceedings, Springer, online.
- Cristian S. Calude and José Félix Costa, (guest) editors of a Special Issue of Natural Computing, 8(3), September 2009, Springer, on Physics and Computation, online.
- Cristian S. Calude and José Félix Costa, (guest) editors of a Special Issue of Applied Mathematics and Computation, 215(4), October 15, 2009, Elsevier, on Physics and Computation, online.
- Cristian S. Calude, José Félix Costa, Rudolf Freund, Marion Oswald, and Grzegorz Rozenberg editors of Lecture Notes in Computer Science, volume 5204, Unconventional Computation 7th International Conference, UC 2008, Vienna, Austria, August 25--28, 2008, Proceedings, Springer, online.
- José Félix Costa and Francisco Dória, (guest) editors of a Special Issue of Applied Mathematics and Computation, 178(1), July 1, 2006, Elsevier, on Hypercomputation, online.
Some events (international)
- Member of the program committee of the 9th International Conference on Unconventional Computation UC 2011, FUNDIM laboratory of the Mathematics Department, University of Turku, Finland, June 6--10, 2011.
- I organized with Cristian Calude, Walid Gomaa, Hélia Guerra, and Karl Svozil the Third International Workshop on Physics and Computation 2010, Egypt, August 30 -- September 4, 2010.
- Member of the program committee of the ICALP 2010, 37th International Colloquium on Automata, Languages and Programming, July 5--12, 2010.
- Invited Speaker at the 9th International Conference on Unconventional Computation, UC 2010, Tokyo, June 21--25, 2010.
- I was the general chair of the 8th International Conference on Unconventional Computation, UC 2009, Ponta Delgada, September 7--11, 2009.
- I was invited speaker at the Workshop Complexity Resources in Physical Computation, Oxford University Computing Laboratory, Oxford, UK, August 24--26, 2009.
- Invited speaker at the Conference SPUC09, The Science and Philosophy of Unconventional Computing, Cambridge, UK, March 23--25, 2009.
- Speaker at the Studia Logica International Conference on Logic and the foundations of physics: space, time and quanta -- TRENDS VI, Belgium, Brussels, December 11--12, 2008.
- Invited speaker at the Workshop Grand Challenges of Unconventional Computation, Academia Europaea, Informatics Section, University of Liverpool, September 17, 2008.
- I organized with Cristian Calude the Workshop on Physics and Computation 2008, a satellitte event of the 7th International Conference on Unconventional Computation, UC 2008, Vienna, August 25--28, 2008.
- I was co-chair of the program committee of the 7th International Conference on Unconventional Computation, UC 2008, Vienna, August 25--28, 2008.
- Invited speaker at the International Colloquium on Causality, Meaningful Complexity and Knowledge Construction, University of Rome "Tor Vergata", Rome, June 5--7, 2008.
- Invited speaker at the Conference TAMC 2008, 5th Annual Conference on Theory and Applications of Models of Computation, Xi ' an, China, April 25--29, 2008.
- Invited speaker at the BCTCS on Physics and computation: An essay on the unity of science through computability, April 7--10, 2008.
- Member of the program committee of the 6th International Conference on Unconventional Computation UC 2007, Queen's University, Kingston, Ontario, August 13--17, 2007.
- Invited speaker at a Special Session of the European CiE Conference Computability in Europe 2007: Computation and Logic in the Real World, University of Siena, Siena, June 18--23, 2007.
- Invited speaker at the conference First Lisbon Colloquium for the Philosophy of Science, The Unity of Science: Non Traditional Approaches, October 25--28, 2006.
- Invited speaker at the Workshop Future Trends in Hypercomputation, Sheffield, UK, September 11--13, 2006.
- Speaker at the Conference UC 2006, 5th International Conference on Unconventional Computation, September 4 -- 8, 2006, York, UK. Photos of this beautiful event in York.
- Lecturer at the International Logic and Computer Science Semester at Tel-Aviv (Tel Aviv University), March 10 -- 12, 2004.
Some events (national)
- Invited speaker at the Escola de Inverno de Matemática, Instituto Superior Técnico, February 9--12, 2011.
- Book presentation: «Neuroaesthetics - Can Science Explain Art?», edited by Olga Pombo, Silvia di Marco, and Marco Pina, CFCUL, Fábrica Braço de Prata, 16 Dezembro, 2010.
- Book presentation: «Entre o Conceito e a Imagem. O lugar da Psicanálise na obra de Gaston Bachelard» by Ana Gaspar, CFCUL, Livraria Escolar Editora, FCUL, 14 Maio, 2010.
- Invited speaker at the Seminar «Aproximações ao Conceito de Imagem XX», A Neurobiologia da Arte, organized by CFCUL, June 14, 2010.
- Invited speaker at the Internacional Workshop Bachelard: Conceitos & Imagens, organized by CFCUL, May 14, 2010.
- Invited speaker at the Sessão Inaugural AIA Conferência "Artes, Ciências, Tecnologias", September 21, 2009.
- Invited speaker at the Workshop on Os lugares da Epistemologia e da Poética de Gaston Bachelard, December 10, 2007.
- Invited speaker at the Workshop on Arte e Ciência como Criação: Em torno de Gaston Bachelard, January 26, 2007.
- Invited speaker in the Workshop on Ciência e Filosofia entre Rómulo de Carvalho e António Gedeão, November 24, 2006.
- I was member of the program committee of the II Workshop de Estatística, Matemática e Computação, Universidade Aberta, November 8--9, 2006.
- Co-organizer of the Workshop on Language and Complexity (Calouste Gulbenkian e Oriente foundations), Arrábida, July 5--7, 2004.
- Co-organizer of the Workshop on Soft Computing and Complex Systems, June 23--27, 2003.
Cross-boundaries projects
Seminars of general interest (national)
- Laplace's Daemon, EIM 2011 (session 1), February 9-12.
- Can Science Explain Art?, EIM 2011 (session 2), February 9-12.
- Marya Sklodowska, Dia Internacional da Mulher, Biblioteca da Câmara Municipal de Setúbal, March 2010.
- Newtonian Cosmology, Observatório Astronómico de Lisboa, May 25, 2007.
Current lectures
Other lectures (Senior University UNISETI)
