Identifying sources of global contention in constraint satisfaction search

Much work has been done on learning from failure in search to boost solving of combinatorial problems, such as clause-learning and clause-weighting in boolean satisfiability (SAT), nogood and explanation-based learning, and constraint weighting in constraint satisfaction problems (CSPs). Many of the top solvers in SAT use clause learning to good effect. A similar approach (nogood learning) has not had as large an impact in CSPs. Constraint weighting is a less fine-grained approach where the information learnt gives an approximation as to which variables may be the sources of greatest contention. In this work we present two methods for learning from search using restarts, in order to identify these critical variables prior to solving. Both methods are based on the conflict-directed heuristic (weighted-degree heuristic) introduced by Boussemart et al. and are aimed at producing a better-informed version of the heuristic by gathering information through restarting and probing of the search space prior to solving, while minimizing the overhead of these restarts. We further examine the impact of different sampling strategies and different measurements of contention, and assess different restarting strategies for the heuristic. Finally, two applications for constraint weighting are considered in detail: dynamic constraint satisfaction problems and unary resource scheduling problems.

Investigating relative clauses in children with specific language impairment

Background: It is well documented that children with Specific Language Impairment (SLI) experience significant grammatical deficits. While much of the focus in the past has been on their morphosyntactic difficulties, less is known about their acquisition of complex syntactic structures such as relative clauses. The role of memory in language performance has also become increasingly prominent in the literature. Aims: This study aims to investigate the control of an important complex syntactic structure, the relative clause, by school age children with SLI in Ireland, using a newly devised sentence recall task. It also aims to explore the role of verbal and short-termworking memory in the performance of children with SLI on the sentence recall task, using a standardized battery of tests based on Baddeley’s model of working memory. Methods and Procedures: Thirty two children with SLI, thirty two age matched typically developing children (AM-TD) between the ages of 6 and 7,11 years and twenty younger typically developing (YTD) children between 4,7 and 5 years, completed the task. The sentence recall (SR) task included 52 complex sentences and 17 fillers. It included relative clauses that are used in natural discourse and that reflect a developmental hierarchy. The relative clauses were also controlled for length and varied in syntactic complexity, representing the full range of syntactic roles. There were seven different relative clause types attached to either the predicate nominal of a copular clause (Pn), or to the direct object of a transitive clause (Do). Responses were recorded, transcribed and entered into a database for analysis. TheWorkingMemory Test Battery for children (WMTB-C—Pickering & Gathercole, 2001) was administered in order to explore the role of short-term memory and working memory on the children’s performance on the SR task. Outcomes and Results: The children with SLI showed significantly greater difficulty than the AM-TD group and the YTD group. With the exception of the genitive subject clauses, the children with SLI scored significantly higher on all sentences containing a Pn main clause than those containing a transitive main clause. Analysis of error types revealed the frequent production of a different type of relative clause than that presented in the task—with a strong word order preference in the NVN direction indicated for the children with SLI. The SR performance for the children with SLI was most highly correlated with expressive language skills and digit recall. Conclusions and Implications: Children with SLI have significantly greater difficulty with relative clauses than YTD children who are on average two years younger—relative clauses are a delay within a delay. Unlike the YTD children they show a tendency to simplify relative clauses in the noun verb noun (NVN) direction. They show a developmental hierarchy in their production of relative clause constructions and are highly influenced by the frequency distribution of the relative clauses in the ambient language.