Verónica Becher
Verónica Becher
Director of   KAPOW   Kapow group, Departamento de Computación, FCEyN, UBA
Associate Professor , Departamento de Computación, FCEyN,UBA
Researcher CONICET (Investigadora Independiente)
Chercheuse Laboratoire International Associée INFINIS (Université Paris 7-Universidad de Buenos Aires): INformatique Fondamentale, logIque, laNgages, vérIfication et Systèmes.
Area   Theoretical computer science, program-size complexity, algorithmic randomness, problems on words.

Address
Departmento de Computación , Facultad de Ciencias Exactas y Naturales
Universidad de Buenos Aires
Pabellón I, Ciudad Universitaria, (C1428EGA) Buenos Aires, Argentina
E-mail: vbecher@dc.uba.ar

Slow Science http://slow-science.org/- La désexcellence

Soon       Alan Turing Year     Alan Turing year 2012
Organizer Dagstuhl seminar Computability, Complexity and Randomness 2012, Schloss Dagstuhl, Seminar 12021, January 8-13, 2012.
Visiting Fellow Isaac Newton Institute for Mathematical Sciences , Semantics and Syntax - A Legacy of Alan Turing, Cambridge UK, July 2012.
Invited speaker in Turing Centenary Conference CiE 2012 - How the World Computes, Cambridge UK, 18 -23 June 2012.
7th Conference on Computability, Complexity and Randomness CCR 2012 Isaac Newton Institute, Cambridge UK, July 2-6, 2012.
Logic Workshop at Buenos Aires A Tribute to Horacio Arló-Costa. SADAF, Buenos Aires, August 2-4, 2012.
IV Congreso Latinoamericano de Matemática (CLAM) FAMAF, Universidad Nacional de Córdba, 6-10 Agosto 2012.
WoLLIC 2012 (19th Workshop on Logic, Language, Information and Computation), Buenos Aires, September 3-6, 2012.
Buenos Aires Semester in Computability Complexity and Randomness, January to June 2013.

Teaching in 2012
Algoritmos y Estructuras de Datos I

Información y Azar (course taught with Gregory Chaitin several years)
Current Projects
Binational project Argentina-France, MINCyT-INRIA/CNRS, FRIC08/01, Laboratoire d'Informatique Algorithmique: Fondements et Applications (LIAFA) CNRS - Université Paris 7, Denis Diderot. Jean Eric Pin / Verónica Becher, "Aléatorieté et combinatoire des mots", 2009-2011.

Programabilidad versus Computabilidad, PICT 2067, Agencia Nacional de Promoción Científica y Tecnológica, 2008-2010. UBACyT X098, 2008-2011.

PICT 525, Agencia Nacional de Promoción Científica y Tecnológica, 2011-2014. UBACyT 20020100100945, 2011-2014. Dirección: Joos Heintz. Codirección: V. Becher.

Binational project Argentina-Spain, AR2009-009, "The Homogenization Dynamics of Eukaryotes Genomes", Hernan Dopazo (Príncipe Felipe, España) - Verónica Becher (UBA), 2010-2011.

Publications

V.Becher, P.Heiber. "A linearly computable measure of string complexity", Theoretical Computer Science, in press, 2012.

V.Becher, S.Grigorieff. "Wadge hardness in Scott spaces and its effectivization", submittted.

V.Becher, S.Grigorieff. "Borel and Hausdorff hierarchies in Scott spaces and their effectivization", submitted.

V.Becher. "Turing's normal numbers: towards randomness", to appear in LNCS volume of CiE 2012.

V.Becher, P.Heiber. On extending de Bruijn sequences. Information Processing Letters 111,930-932, 2011.

V.Becher. Turing's note on normal numbers. In Alan Turing - his work and impact, Editors: S Barry Cooper and Jan van Leeuwen, Elsevier, 2012

V.Becher, P.Heiber, A.Deymonnaz. "Efficient computation of all perfect repeats in genomic sequences of up to half a Gigabyte, with a case study on the Human genome.", Bioinformatics 25(14):1746-1753, 2009.

V.Becher, S.Grigorieff. "From index sets to randomness in \emptyset^n. Random reals and possibly infinite computations", Journal of Symbolic Logic, 74:1, 124--156, 2009.

V. Becher, S. Grigorieff. "Random reals a la Chaitin with or without prefix freeness", Theoretical Computer Science 385, 193--201, 2007.

V.Becher, S.Figueira, R. Picchi. "Turing's unpublished algorithm for normal numbers", Theoretical Computer Science, Volume 377 , 126-138, 2007.

V.Becher, S.Figueira, S.Grigorieff, J.Miller. "Randomness and Halting Probabilities" , Journal of Symbolic Logic 71:4, pp.1411--1430, 2006.

V.Becher and S.Grigorieff. "Random Reals and Possibly Infinite Computations. Part I: randomness in \emptyset'" , Journal of Symbolic Logic, 70, 3, pp.891-913, 2005.

V.Becher, S.Figueira, A. Nies, S. Picchi. "Program size complexity for possibly infinite computations", Notre Dame Journal of Formal Logic 51-64, 2005.

V. Becher, S. Grigorieff. "Recursion and Topology on 2^{\leq \omega} for possibly Infinite computations", Theoretical Computer Science, 322 (1), pp. 85-136, 2004

V. Becher and S. Figueira, "Kolmogorov Complexity for Possibly Infinite Computations", Journal of Logic Language and Information, Volume 14, Number 2, 133 --148, 2005.

V. Becher and G. Chaitin, "Another example of higher order randomness", Fundamenta Informaticae, Vol. 51:4, . 325--338, 2002.

V. Becher and S. Figueira, "An example of a computable absolutely normal number", Theoretical Computer Science, Vol.270, 947--958, 2002.

V. Becher, S.Daicz and G.Chaitin, "A highly random number", Combinatorics, Computability and Logic, C.Calude, M. J.Dineen and S.Sburlan (eds), Springer Verlag, London, 55--68, 2001.

V. Becher C.Areces, "Iterable AGM functions", Frontiers of Belief Revision, H.Rott and M.Williams (eds),Kluwer, Dordrecht, 261--277, 2001.

V.Becher, C.Areces and S.Ferro, "Characterization Results for d-Horn Formulas, or On formulas that are true on Dual Reduced Products". Logic, Language and Computation, Volume 3, Cavedon, P.Blackburn, N.Braisby and A. Shimojima.(eds), CSLI Publications, 49--66, 2000.

V. Becher and C.Areces, "Update, the infinite case", Proceedings of the Argentinean Workshop on Theoretical Computer Science, in the 28 Jornadas Argentinas de Informáatica e Investigación Operativa (JAIIO), Buenos Aires, September 1999.

V. Becher, Fermé, Lazzer, Rodriguez, Oller and Palau, "Some Observations on Carlos Alchourrón's Theory of Defeasible Conditionals". Norms Logics and Information Systems, P.Mc Namara and H. Prakken (eds), New Studies on Deontic Logic and Computer Science, IOS Press, 219--230, 1999.

C. Boutilier and V. Becher, "Abduction as Belief Revision", Journal of Artificial Intelligence, 77(1), 43--94. 1995.

This is the extended version of the conference paper "A Model of Preferred Explanations", Eleventh National Conference on Artificial Intelligence (AAAI93), Washington DC, 642--648, 1993.

V.Becher, "Two Conditional Logics for Defeasible Inference: A Comparison. Preliminary Version", Lecture Notes in Computer Science; Notes in Artificial Intelligence, J. Wainer, A. Carvalho A. (eds), Advances in Artificial Intelligence. Springer Verlag, Berlin, 49--58, 1995.

V.Becher, "Unified Semantics for Revision and Update, or the Theory of Lazy Update", Proceedings of the 24 Jornadas Argentinas de Informática e Investigación Operativa (JAIIO), SADIO (eds). Buenos Aires, Argentina, 1995.


Talks and conferences
- "A better complexity of finite sequences" Invited talk at Computability, Complexity and Randomness (CCR 2011), Cape Town, Jan 31 to February 4, 2011, co-located with the Eighth International Conference on Computability and Complexity in Analysis (CCA 2011). slides

-"Efficient algorithms fror genomic sequence analysis", reunión científica STIC-AMSUD, Departamento de Computación, FCEyN, UBA, November 5, 2010.

- "Deep into Genomes: Looking for Perfect Repeats in Eukaryote Genomes", P. Barenbaum, V. Becher, A. Deymonnaz, M. Halsband, P. Heiber, J. Herrero, H. Dopazo, Groupement De Recherche Européen (GDRE), Comparative Genomics Meeting, 16-17, November 2010, Barcelona, Spain.

-Plenary conference, 1er Congreso Argentino de Bioinformática y Biología Computacional, Mayo 14,2010, Universidad Nacional de Quilmes, Buenos Aires.

-"A new efficient algorithm to find all DNA repeats with exact matching", in 24th IFIP conference on System Modelling and Optimization, 27 - 31 July 2009 Buenos Aires, Argentina, 2009.

-Invited seminar talk "Perfect repeats in te human genome, an exhaustive but efficient computation", IBM Life Science, Watson Research, Newy York, July 22, 2009.

-"Effective hard sets", with Serge Grigorieff, Fourth International Conference in in Computability, Complexity and Randomness 29 June to July 3rd, 2009, CIRM center at Lumniny, Marseille, France.

-Invited seminar talk, "Perfect repeats in te human genome, an exhaustive but efficient computation", IFIBYNE-CONICET, Depto. Fisiología, Biología Molecular y Celular, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, May 7, 2009.

-Invited talk, "What do different chromosomes have in common? An exhaustive but efficient computation", Center for Genomic Regulation, Barcelona, España, January 27, 2009.

-Invited seminar talk, "What do different chromosomes have in common? An exhaustive but efficient computation", Instituto de Investigaciones Príncipe Felipe, Valencia, España, January 23, 2009.

-"Random reals from usual mathematical notions", Computability, Complexity and Randomness", Nanjing China, 18 May 2008.

-Invited talk "Wadge Hardness and Randomness" at Seminar on Topological and Game Theoretic Aspects of infinite computations, Schloss Dagstuhl, Wadern, Germany, June to 4 July 2008.

-"Eulerian sequences in de Bruijn graphs", talk at the Séminaire Complexité, Logique et Informatique, Paris 7, LIAFA, Université Paris Diderot, February 2008.

-"Cycles in de Bruij graphs", talk in "Jouurné de 60 ans de Serge Grigorieff, Université Paris Diderot, 15 janvier 2008.

-"Números reales aleatorios", conferencia plenaria invitada, Unión Matemática Argentina, FAMAF, Universidad de Córdoba, 21 de septiembre de 2007.

-"Turing's unpublished algorithm for normal numbers", conferencia plenaria invitada, XIII Simposio Latinoamericano de Lógica Matemática, Oaxaca México, 10 Agosto 2006.

-"On the old problem of a definition of randomness useful in practice", charla invitada Workshop on Effective randomness, Palo Alto, 7 al 10 de Agosto 2006.

-"Turing's unpublished algorithm for normal numbers", Turing days, Bilgi Universitesi, Istambul, 27 May 2006.

-Turing's unpublished algorithm for normal numbers", Seminar on Kolmogorov Complexity and Applications, Schloss Dagstuhl, Enero 2006.

-"Cornucopia of randomness", Meeting in honor of Joos Heintz's 60th birthday, Third international workshop on seminumerical techniques in polynomial equation solving,Buenos Aires, October 24-28, 2005.

-"Old and new results in Program size complexity", LIAFA, Paris 7, France, March 2005.

-"High Randomness in the spirit of Rice's theorem for computability", Department of Mathematics and Computer Science, University of Victoria, Wellington, New Zealand, Noviembre 2004.

-"A conjecture on Randomness in the spirit of Rice's theorem", XII Latin American Symposium on Mathematical Logic, San José, Costa Rica, 12-16 January 2004.

-"Is Complexity reusable?" Primeras Jornadas Latinoamericanas de Ingeniería y Desarrollo de Software. Microsoft Argentina, Pabellón Blanco de La Rural, October 30, 2003. Panelists: Verónica Becher, Yuri Gurevich , Joos Heintz.

-"Randomness and Infinite Computations", Seminar on Kolmogorov Complexity and Applications, Dagstuhl, Wadern, Germany, April 2003.

-"Program size complexity in possibly infinite computations", with S. Figueira y A. Nies, Workshop on Computability and Randomness, Ruprecht-Karls-Universitat Heidelberg, Germany, April 2003.

-"Randomness: solved and unsolved questions", Ecole Normal Superieure, Paris, January 2002.

-"On the Standard proof of randomnes", King's College, London, UK, January 2002.

-"On the Standard proof of randomness", ILLC, University of Amsterdam, The Netherlands, January 2002.

-"A Highly Random Number", Discrete Mathematics and Theoretical Computer Science, Constanta, Rumania, July 2001.

-"Randomness and real numbers". CREA -Ecole Polytechnique, Paris, July 2001.

-"Examples of higher order randomness", XIV Coloquio Latinoamericano de Algebra, La Falda, Córdoba, Argentina, July 2001.

-"El azar y los números reales". Dept.de Física, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, June 2001.

-"El azar y los números reales", FAMAF, Universidad de Córdoba, Argentina, July 2001.

-"Una Función de cambio Analítico", con Christian Durr, Workshop on Theory Change and Theory of Conditionals, Buenos Aires, December 2001.

-"Incompletitud y Azar", Sociedad Argentina de Análisis Filosófico (SADAF), December 1998.

-"A comparison between two defeasible conditionals in standard modal logics", Coloquio de Filosofía Teórica, SADAF, July 1995.

-"Unified semantics for Revision and Update", Department of Computer Science, The University of British Columbia, January 1995.


Notes related to my research
The Omega Man New Scientist, 10 de Marzo, 2001.
Omega, entrevista con Gregory Chaitin, diario La Nación, Buenos Aires, 29 Abril, 2001.
Perfume de Azar, nota en el diario Páagina 12, 13 de Julio 2002.
Números casuales, Exactamente, revista de la Facultad de Ciencias Exactas y Naturales, Diciembre 2003.
De puzzles, soluciones y cuelgues de computadoras, Oficina de prensa -SEGBE, Numero 593, año 16, 24 Octubre 2005

Other
Las Computadoras y el Azar, Facultad de Ciencias Exactas y Naturales, Semana de la Computación, Octubre 2001.
Cuánto de Golem hay en las computadoras? Proyecto Golem 2003 - 5764 Buenos Aires-Praga. El Golem en la Religión y en las Artes y como Metáfora en las Ciencias de la Computación. Museo Nacional de Bellas Artes. Buenos Aires, 2 y 3 octubre 2003.
Golem's stomachs or a hippie dream? Proyecto Golem 2005, bienal argentino-checa, Praga, 2 al 5 de Julio 2005.
Organizadora de Concursos de cuentos y ensayos por los 50 años de Clementina, 2011

Curso "Información y Azar", Reunión Anual de la Unión Matemática Argentina, Universidad Nacional del Centro de la Provincia de Buenos Aires, Tandil, 27 de septiembre al 2 de octubre de 2010.

We organized
Conference on Logic, Computability and Randomness, September 20 to 24,  2004. Córdoba, Argentina
Conference on Logic, Computability and Randomness, January 10 to 13,  2007. Buenos Aires, Argentina

Concurso de cuentos y ensayos históricos por los 50 anos de Clementina, la primera computadora científica del país. Agosto 2011, Buenos Aires, Argentina.

Chercheur étranger de la Mairie de Paris en qualité de senior CNRS et Université Paris 7, Laboratoire d'Informatique Algorithmique: Fondements et Applications (LIAFA) et Équipe de logique mathématique, November 2008 to February 2009.

Research supervision
Director of "Tesis de Licenciatura" in Computer Science (equivalent to MSc. thesis)
19. Alejandro Alfonso, en curso 2011.
18. Facundo Lopez Britost, en codireccion con Pablo Heiber. Con beca CIN, en curso 2011
17. Leandro Miquet, en codireccion con Esteban Hasson, en curso 2011
16. Alejandro Deymonnaz, en curso 2011
15. Melisa Halsband, Diciembre 2010.
14. Lucia Cavatorta. Sobre el numero de Champernowne, Diciembre 2009
13. Marcos Foglino. Identificacion biologica de patrones genoma humano, 2009
12. Jose Orlicki. Sobre la entropia algoritmica en maquinas reversibles. Con beca de estudiante UBACyT, 2006.
11. Rafael Picchi, Sobre el manuscrito de Alan Turing "A note on normal numbers", Diciembre 2005. Premiada Fundación Sadosky.
10. Mariano Moscato, Sobre la entropía algorítmica de objetos abstractos, Junio 2005.
9. Martín Urtasun y Alejo Capparelli, Clasificacion automtica de documentos basada en la metrica de similitud universal de Vitanyi, Diciembre 2004. Premio Microsoft IDS 2003.
8. Alejandro Dau, Secuencias Maximizadotas de Subcadenas ¬¨¬®‚àö‚àèCuán aleatorias son?, Junio 2004.
7. Silvana Bonaccio y Rosana Centrone, Una maquina universal de Chaitin en Prolog, Dic. 2002
6. Silvana Picchi. Otra Caracterizacion de reales computablemente enumerables, Noviembre 2002.
5. Fernando Calderon,Diego Calderon,Norma Marinaro, Un algoritmo para la función Safe Contraction, Diciembre 2001.
4. Christian Durr, Definición e implementación de una función de cambio analítico, Noviembre 2001
3. Santiago Figueira, Un ejemplo de un número computable absolutamente normal, Noviembre 2000.
2. Sergio Daicz, Una nueva versión de la probabilidad de detención, Agosto 2000.Premiada tercer lugar en el VIII Concurso de Tesis de Maestria CLEI-UNESCO 2001.
1. María de los Angeles Grieco, Programas elegantes en Prolog, julio 1999.

Director of doctoral thesis in Computer Science
Pablo Heiber, desde 2009. Con beca doctoral CONICET.
Santiago Figueira, "Aspectos de aleatoriedad", con beca Fundación Antorchas, Fundacion YPF y beca doctoral CONICET. Mayo 2006.Calificación maxima.
Co-dirección tesis doctoral Daniel Gorín en cotutela UBA-Universidad Nancy,Francia, con beca doctoral CONICET, tesis defendida en Diciembre 2009. Calificacion máxima.
Co-direccion tesis doctoral Sergio Mera en cotutela UBA-Universidad Nancy,Francia, con beca doctoral CONICET, tesis defendida en Diciembre 2009. Calificacion maxima.

Director of Fellowships project IBM-Biosidus, 2009-2010
Pablo Barenbaum
Alejandro Deymonnaz
Melisa Halsband
Pablo Heiber

Biographical note
I graduated in Computer Science (FCEyN, Universidad de Buenos Aires) in 1990. I was lucky to participate in Carlos Alchourrón's seminar where we studied his formalization of the problems of expansion, derogation and amendment in law; this is known today as the AGM model, for their authors Alchourrón, Gardenfors and Makinson.

From 1991 to 1993 I did a Master in Science in Computer Science at The University of British Columbia, Vancouver, Canada, directed by Craig Boutilier. My MSc. thesis gives a model of preferred explanation based on the AGM model.

Back in Buenos Aires, I did my doctoral studies (FCEyN, Universidad de Buenos Aires) directed by Carlos Alchourrón and graduated in 1999. Informally David Makinson acted as my supervisor after Alchourrón passed away. My thesis extends the AGM model to solve two problems: iterated changes, and the changes in unions and intersections.

In my postdoctoral research I entered into algorithmic randomness under the supervision of Gregory Chaitin. I worked on the problem of finding new examples of random real numbers, and I defined plenty Omega numbers that are random in higher levels of the Arithmetical Hierarchy. These Omega numbers are meaningful in terms of computer input/output behaviour.

My work on randomness now continues with Serge Grigorieff (LIAFA, Université Paris 7, Denis Diderot). And since 2009 I lead the research group KAPOW, where we work on problems about randomness of finite and infinite words, and we try to solve them by integrating combinatorics, algorithms, and complexity.

esearch group KAPOW, where we work on problems about randomness of finite and infinite words, and we try to solve them by integrating combinatorics, algorithms, and complexity.