On balanced CSPs with high treewidth

Tractable cases of the binary CSP are mainly divided in two classes: constraint language restrictions and constraint graph restrictions. To better understand and identify the hardest binary CSPs, in this work we propose methods to increase their hardness by increasing the balance of both the constraint language and the constraint graph. The balance of a constraint is increased by maximizing the number of domain elements with the same number of occurrences. The balance of the graph is defined using the classical definition from graph the- ory. In this sense we present two graph models; a first graph model that increases the balance of a graph maximizing the number of vertices with the same degree, and a second one that additionally increases the girth of the graph, because a high girth implies a high treewidth, an important parameter for binary CSPs hardness. Our results show that our more balanced graph models and constraints result in harder instances when compared to typical random binary CSP instances, by several orders of magnitude. Also we detect, at least for sparse constraint graphs, a higher treewidth for our graph models.

Statistical modelling of CSP solving algorithms performance

The goal of this work is to try to create a statistical model, based only on easily computable parameters from the CSP problem to predict runtime behaviour of the solving algorithms, and let us choose the best algorithm to solve the problem. Although it seems that the obvious choice should be MAC, experimental results obtained so far show, that with big numbers of variables, other algorithms perfom much better, specially for hard problems in the transition phase.

Representación simbólica de preguntas: el proyecto ReSim

En aquest article presentem el projecte ReSim: representació simbòlica de preguntes, que ha consistit en la creació d'un sistema automàtic capaç de representar en un llenguatge formal una pregunta en llenguatge natural. Tenint en compte la complexitat de l'objectiu, el projecte es va centrar en un àmbit temàtic concret. El tipus de representació usada està basada en el model de les Estructures Lèxico-Conceptuals de Jackendoff 1990.

El desenvolupament de la morfologia verbal: l'imperfet nord-occidental en la producció infantil

L'objectiu d'aquest article és contribuir a l'estudi de la morfologia verbal catalana, en aquest cas amb dades relatives a la varietat nord-occidental. Les formes que forneixen la part descriptiva corresponen a mostres de producció oral obtingudes en informants de 3 -4, 6- 7 i 11- 12 anys, la qual cosa signi ca una descripció morfològica del període de desenvolupament lingüístic del nen. Pel que fa a la interpretació dels resultats es proposa una perspectiva d'anàlisi que inclou tant les consideracions que tenen a veure amb aspectes interns del llenguatge com amb els de caràcter extern.

La reflexió metalingüística en el treball de grup

En aquest article s'analitzen quatre factors que poden incidir en el desenvolupament i el resultats de les tasques de reflexió metalingüística quan es realitzen en grup: tipus de tasca, formes d'interacci ó del grup, condici ó de monolingüe o bilingüe dels participants i llengua objecte de reflexió. Les dades analitzades provenen de la gravació i transcripci ó d'un seguit de sessions de treball en grup en les quals es proposava a nois i noies de secundària (14-15 anys) diferents tasques de tipus metalingüístic. Com a complement de l'an àlisi dels quatre factors esmentats, l'article tamb e inclou un apartat on es compara el proc és de reflexió que segueixen els estudiants de secundària amb el procés que segueixen alumnes del Curs d'Aptitud Pedag ògica (CAP).