Treewidth: theory and applications to computer science

This report is an introduction to the concept of treewidth, a property of graphs that has important implications in algorithms. Some basic concepts of graph theory are presented in the first chapter for those readers that are not familiar with the notation. In Chapter 2, the definition of treewidth and some different ways of characterizing it are explained. The last two chapters focus on the algorithmic implications of treewidth, which are very relevant in Computer Science. An algorithm to compute the treewidth of a graph is presented and its result can be later applied to many other problems in graph theory, like those introduced in the last chapter.

Una aproximación a la situación de la mujer en los estudios universitarios de informática

[ES]En los últimos años, la baja participación de la mujer y la tendencia al descenso de los porcentajes de alumnas matriculadas en los estudios universitarios de informática ha sido objeto de estudio para investigadoras/es en Estados Unidos, Europa y otros países. Habiendo constatado también en la Facultad de Informática de San Sebastián (FISS) de la Universidad del País Vasco (UPV/EHU) dicho descenso, nuestro objetivo ha sido recopilar información estadística para determinar si esta tendencia se ha producido también en otras universidades del Estado español. El estudio incluye, en primer lugar,porcentajes de mujeres inscritas en Ingeniería Informática comparados con los porcentajes en el área técnica en su conjunto. Por otra parte, recoge datos del tercer ciclo y porcentajes de profesoras de los departamentos que imparten docencia en la FISS, comparados con los porcentajes en los mismos departamentos en el conjunto del Estado. Por último, se presentan datos de inserción en el mundo laboral para las promociones 1998-2002 de egresadas/os en la UPV/EHU. Los datos revelan los bajos porcentajes de mujeres que se han matriculado en Ingeniería Informática los últimos años y la tendencia al descenso, las diferencias entre distintas universidades,y que apenas hay sesgo de género en los datos de inserción en el mundo laboral.

Virtual Reconstruction of the Ancient State of a Ruined Church

Contributed to: 4th International Conference, EuroMed 2012, Limassol, Cyprus, October 29 – November 3, 2012.

An Open and Social Spaced Repetition System for Language Learning

In the last decades big improvements have been done in the field of computer aided learning, based on improvements done in computer science and computer systems. Although the field has been always a bit lagged, without using the latest solutions, it has constantly gone forward taking profit of the innovations as they show up. As long as the train of the computer science does not stop (and it won’t at least in the near future) the systems that take profit of those improvements will not either, because we humans will always need to study; Sometimes for pleasure and some other many times out of need. Not all the attempts in the field of computer aided learning have been in the same direction. Most of them address one or some few of the problems that show while studying and don’t take into account solutions proposed for some other problems. The reasons for this can be varied. Sometimes the solutions simply are not compatible. Some other times, because the project is an investigation it’s interesting to isolate the problem. And, in commercial products, licenses and patents often prevent the new projects to use previous work. The world moved forward and this is an attempt to use some of the options offered by technology, mixing some old ideas with new ones.

An Algebraic Preservation Theorem for Aleph-Zero Categorical Quantified Constraint Satisfaction

23 p. -- An extended abstract of this work appears in the proceedings of the 2012 ACM/IEEE Symposium on Logic in Computer Science

Beyond Q-Resolution and Prenex Form: a Proof System for Quantified Constraint Satisfaction

We consider the quanti fied constraint satisfaction problem (QCSP) which is to decide, given a structure and a first-order sentence (not assumed here to be in prenex form) built from conjunction and quanti fication, whether or not the sentence is true on the structure. We present a proof system for certifying the falsity of QCSP instances and develop its basic theory; for instance, we provide an algorithmic interpretation of its behavior. Our proof system places the established Q-resolution proof system in a broader context, and also allows us to derive QCSP tractability results.