José Félix Costa (Theoretical Computer Science)

Associate Professor (with Habilitation)

Recent relevant events (international)

• I am organizing with Cristian Calude, Walid Gomaa, Hélia Guerra, and Karl Svozil the Third International Workshop on PHYSICS AND COMPUTATION 2010, P&C 2010, donwstream the Nile, Egypt, August 30 -- September 3, 2010.
• I am member of the program committee of the ICALP 2010, 37th International Colloquium on Automata, Languages and Programming, July 5--12, 2010.
• I was the general chair of the 8th International Conference on Unconventional Computation, UC 2009, Ponta Delgada, September 7--11, 2009. To be published in the EATCS Bulletin: Report.
• I was invited speaker at the Workshop Complexity Resources in Physical Computation, Oxford University Computing Laboratory, Oxford, UK, 24--26 August, 2009.
• I organized with Cristian Calude a Workshop on PHYSICS AND COMPUTATION, a satellitte event of the 7th International Conference on Unconventional Computation, UC 2008, Vienna, August 2008.
• I was co-chair of the program committee of the 7th International Conference on Unconventional Computation, UC 2008, Vienna, August 2008.

Recent relevant events (national)

• I was invited speaker at the Sessão Inaugural AIA Conferência "Artes, Ciências, Tecnologias", September 21, 2009.

(Some) Workshops and Conferences

• I was in the program committee of the Sixth International Conference on Unconventional Computation (UC'07), Queen's University, Kingston, Ontario, 13--17 August 2007.
• 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.
• I organized the Workshop on Language and Complexity (Calouste Gulbenkian e Oriente foundations), July 5--7, 2004.
• I was organizer and lecturer of the Workshop on Soft Computing and Complex Systems, June 23--27, 2003.

Steering Committee

• I am member of the SC of the series of Workshops in Physics and Computation, now in its SECOND EDITION.

American Mathematical Society (a few reviews)

• 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.

(Some) Reviews A nova ciência da complexidade, Review of At Home in the Universe. The Search for the Laws of Self-Organization and Complexity, by Stuart Kauffman, Oxford University Press, 1995. Disputatio, 1:44--47, 1996.   European Association for Theoretical Computer Science (articles) Physical experiments as oracles, by Edwin Beggs, John V. Tucker, and myself, Bulletin of the European Association for Theoretical Computer Science, 97:137--151, February 2009. What lies beyond the mountains, computational systems beyond the Turing limit, by Jerzy Mycka and myself, Bulletin of the European Association for Theoretical Computer Science, 85:181--189, February 2005.   Homage Homage. Dr. Maria do Céu Novais Faria: The katabasis in Virgil, Ovid, and Camões.   Books Génese da Revolução Astronómica (The Astronomical Revolution), is available at Escolar Editora. I coordinated the Adison-Wesley portuguese edition of Alonso and Finn's PHYSICS.

(Some) Recent articles

• Physical experiments and the limits of computation, by Edwin Beggs, John V. Tucker, and myself, Journal Article. Download the ABSTRACT.
• Physical oracles: the Turing machine and the Wheatstone bridge, by Edwin Beggs, John V. Tucker, and myself, Special Issue of Studia Logica, The Contributions of Logic to the Foundations of Physics, Trends in Logic VI, Diederik Aerts, Sonja Smets, and Jean Paul Van Bendegem (editors), Springer, 2010, to appear. Studia Logica. Download the PREPRINT.
• Limits to measurements in experiments governed by algorithms, by Edwin Beggs, John V. Tucker, and myself, Journal Article. Download the PREPRINT.
• Comparing complexity classes relative to physical oracles, by Edwin Beggs, John V. Tucker, and myself, Journal Article.
• Oracles and advice as measurements, by Edwin Beggs, Bruno Loff, John V. Tucker, and myself, Journal Article. Download the PREPRINT.
• Processes with infinite liveness requirements, by Hélia Guerra and myself, Journal Article.
• Computational Models of Measurement and Hempel's Axiomatization, by Edwin Beggs, John V. Tucker, and myself, Book Chapter, Series: Theory and Decision Library A, Vol. 46:155--184, Springer, 2009. Download the PREPRINT.
• Introduction to the Special Issue on Physics and Computation, by Cristian S. Calude and myself, Applied Mathematics and Computation, 215(4): 1309--1310, Elsevier, October 15, 2009.
• Abstract: Quanta in classical mechanics: uncertainty in space, time, energy, by Edwin Beggs, John V. Tucker, and myself, Studia Logica International Conference on Logic and the Foundations of Physics: Space, Time and Quanta, Trends in Logic VI, 2009.
• Unifying science through computation: Reflections on computability and physics, by Edwin Beggs, John V. Tucker, and myself, New Approaches to the Unit of Science, Volume II (Special Sciences and the Unity of Science), John Symons, Juan Manuel Torres and Olga Pombo (eds.), Book series: Logic, Epistemology, and the Unity of Science, Springer, in print. Download the PREPRINT.
• Introduction to the Special Issue on Physics and Computation, by Cristian S. Calude and myself, Natural Computing, 8(3):429--430, Springer, September, 2009.
• A foundation for real recursive function theory, by Bruno Loff, Jerzy Mycka, and myself, Annals of Pure and Applied Logic, 160(3): 255--288, 2009.
• Computational complexity with experiments as oracles. II. Upper bounds, by Edwin Beggs, Bruno Loff, John V. Tucker, and myself, 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 myself, The Journal of Logic and Algebraic Programming, 78(3):117--137, 2009.
• Five views of hypercomputation, by Bruno Loff and myself, International Journal of Unconventional Computing, 5(3--4): 193--207, Special Issue on Hypercomputation, Old City Publishing, Inc., 2009.
• Differential equations, infinite limits and real recursive functions, by Bruno Loff, Jerzy Mycka, and myself, Journal Article, WSEAS Press, 2009.
• Oracles and advice as measurements, by Edwin Beggs, Bruno Loff, John V. Tucker, and myself, Cristian S. Calude et al. (eds.), 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, Bruno Loff, John V. Tucker, and myself, Proceedings of the Royal Society, Series A (Mathematical, Physical and Engineering Sciences), 464(2098):2777--2801, October 8, 2008.
• On the complexity of measurement in classical physics, by Edwin Beggs, Bruno Loff, John V. Tucker, and myself, invited paper, M. Agrawal, D. Du, Z. Duan, and A. Li (eds.), 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, Francisco Coelho, and myself, International Journal of Unconventional Computing, 4(3): 223--248, Special Issue Towards a Theory of Unconventional Computing, Old City Publishing, Inc., 2008.
• Introduction to the Special Issue on Hypercomputation, by Francisco Dória and myself, Applied Mathematics and Computation, 178(1):1--3, Elsevier, July 2006.

(Some) Other articles

• Our first article on real-valued recursive functions: From recursive to R-recursive functions, by Manuel Campagnolo and myself, 1997.
• The abstract immune system algorithm, by Daniel Pacheco and myself, in Selim G. Akl, Cristian S. Calude, Michael J. Dinneen, Grzegorz Rozenberg, and H. Todd Wareham (eds.), Unconventional Computation 2007, UC ' 07, Kingston, August 13-17, Lecture Notes in Computer Science 4618:137--149, Springer, 2007. Immune Lab.
• The new promise of analog computation, by Bruno Loff, Jerzy Mycka and myself, invited paper, in S. Barry Cooper, Benedikt Loewe, and Andrea Sorbi (eds.), Computability in Europe, CiE 2007, Siena, Italy, June 18-23, 2007, Computation and Logic in the Real World, Lecture Notes in Computer Science 4497: 189--195, Springer, 2007.
• Computability on reals, infinite limits and differential equations, by Bruno Loff, Jerzy Mycka, and myself, Applied Mathematics and Computation, 191(2):353--371, Elsevier, 2007.
• A new conceptual framework for analog computation, by Jerzy Mycka and myself, Theoretical Computer Science, 374(1--3):277--290, Elsevier, 2007.
• Undecidability over continuous-time, by Jerzy Mycka and myself, Logic Journal of the IGPL, 14(5):649--658, Oxford University Press, 2006.
• The P =/= NP conjecture in the context of real and complex analysis, by Jerzy Mycka and myself, Journal of Complexity, 22(2):287--303, Elsevier, 2006.
• Euclid abstract machine: the trisection of the angle and the halting problem, by Jerzy Mycka, Francisco Coelho, and myself, Cristian S. Calude, Michael J. Dinneen, Gheorghe Paun, Grzegorz Rozenberg, and Susan Stepney (eds.), York, September 4-8, Lecture Notes in Computer Science 4135: 195--206, Springer, 2006.
• Real recursive functions and their hierarchy, by Jerzy Mycka and myself, Journal of Complexity, 20(6): 835--857, Elsevier, 2005.
• The computational power of continuous dynamic systems, by Jerzy Mycka and myself, Maurice Margenstern (ed.), Machines, Computations, and Universality, MCU 2004, Lecture Notes in Computer Science, 3354:164--175, Springer-Verlag, 2004.
• A compiler and simulator for partial recursive functions over neural networks, by João Neto, Paulo Carreira, Miguel Rosa, and myself, Ahmad Lotfi and Jonathan M. Garibaldi (eds), Applications and Science in Soft Computing, Springer-Verlag, 2004, 39--46.
• Analog computers and recursive functions over the reals, by Daniel Graça and myself, Journal of Complexity, 19(5):644--664, 2003.
• Symbolic processing in neural networks, by João Pedro Neto, Hava T. Siegelmann, and myself, Journal of the Brazilian Computer Society, 8(3):58--70, 2003.
• An analog characterization of the Grzegorczyk hierarchy, by Manuel Campagnolo, Cris Moore, and myself, Journal of Complexity, 18(4):977--1000, 2002.
• Canonical Institutions of Behaviour, by Hugo Lourenço and myself, Maura Cerioli and Gianna Reggio (eds.), Lecture Notes in Computer Science, 2267:71--84, Springer-Verlag, 2001.
• Verifying properties of neural nets, by Pedro Rodrigues, Hava T. Siegelmann, and myself, J. Mira and A. Prieto (eds), IWANN'2001, Lecture Notes in Computer Science, 2084:158--165, Springer-Verlag, 2001. MCheck -- A Neural Verifier.
• Iteration, inequalities, and differentiability in analog computers, by Manuel Campagnolo, Cris Moore, and myself, Journal of Complexity, 16(4):642--660, 2000.
• Hypercomputation in the limits of classical physical reality, by myself, Review of Neural Networks and Analog Computation --- Beyond the Turing Limit, by Hava T. Siegelmann, Birkhauser, 1999. ACM Computing Reviews, 41(9):343--345, 2000.
• Nonsequential automata semantics for a concurrent object-based language, by Paulo B. Meneses, Amílcar Sernadas, and myself, Electronic Notes in Theoretical Computer Science, 14(1):245--273, 1998.
• Turing universality of neural nets (revisited), by João Pedro Neto, Hava T. Siegelmann, Carmen P. Suárez Araujo, and myself, F. Pichler and R. Moreno-Díaz (eds), Computer Aided System Technology, EUROCAST'97, Lecture Notes in Computer Science, 1333:361--366, Springer-Verlag, 1997.
• Architectural specifications: Modeling and structuring behavior through rules, by Carlos Paredes, José Luiz Fiadeiro, and myself, in H. Kilov and W. Harvey (eds), Object-oriented Behavioral Specifications, Kluwer Academic Publishers, 1996, 221--240.
• Mirror, mirror in my hand... a duality between specifications and models of process behaviour, by José Luiz Fiadeiro and myself, Mathematical Structures in Computer Science, 6(4):353--373, 1996.
• Synchronization in Petri nets, by Paulo B. Meneses and myself, Fudamenta Informaticae, 26:11--22, 1996.
• Object specification logic, by Amílcar Sernadas, Cristina Sernadas, and myself, Journal of Logic and Computation, 5(5):603--630, 1995.
• Compositional reification of concurrent systems, by Paulo B. Meneses and myself, Journal of the Brazilian Computer Society, 2(1):50--67, 1995.
• Refinement mapping for (discrete event) system theory, by Paulo B. Menezes, A. Sernadas, and myself, F. Pichler, R. Moreno Díaz, and R. Albrecht (eds), Computer Aided System Technology, EUROCAST'95, Lecture Notes in Computer Science, 1030:103--116, Springer-Verlag, 1996.
• Institutions for behaviour specification, by José Luiz Fiadeiro and myself, 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.
• Progress assumption in concurrent systems, by Amílcar Sernadas and myself, Formal Aspects of Computing, 7(1):18--36, 1995.
• Object inheritance beyond subtyping, by Amílcar Sernadas, Cristina Sernadas, and myself, Acta Informatica, 31(1):5--26, 1994.
• An institution of object behaviour, by Amílcar Sernadas, Cristina Sernadas, and myself, 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.
• Espelho, espelho meu... , by José Luiz Fiadeiro and myself, Actas do III Encontro de Algebristas Portugueses, 71--86, Universidade de Coimbra, 1993.
• Data encapsulation and modularity: Three views of inheritance, by Amílcar Sernadas, Cristina Sernadas, and myself, A. Borzyszkowski and S. Sokolowski (eds), Mathematical Foundations of Computer Science 93, Lecture Notes in Computer Science, 711:382--391. Springer-Verlag, 1993.
• A categorial framework of process interconnection, by Amílcar Sernadas and myself, The INESC Journal of Research and Development, 4(1):81--93, 1993.
• Process semantics of temporal logic specification, by José Luiz Fiadeiro, Amílcar Sernadas, Tom Maibaum, and myself, 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 Amílcar Sernadas, Cristina Sernadas, Hans-Dieter Ehrich, and myself, I. Havel and V. Koubek (eds), Mathematical Foundations of Computer Science 92, Lecture Notes in Computer Science, 629:200--208, Springer-Verlag, 1992.
• From processes to objects, by Amílcar Sernadas, Hans-Dieter Ehrich, and myself, The INESC Journal of Research and Development, 1(1):7--27, 1990.
• S-P versus D na Região do Arquipélago dos Açores, by myself, Revista de Estudos Açoreanos, Boletim da Sociedade Afonso Chaves, 4(4):280--331, 1987.
• An analog characterization of the subrecursive functions, by Manuel Campagnolo, Cris Moore, and myself, Research Report 00-01-005, Santa Fe Institute, 2000.
• Iteration, inequalities, and differentiability in analog computers, by Manuel Campagnolo, Cris Moore, and myself, Research Report 99-07-043, Santa Fe Institute, 1999.