Explaining why and how a tree $t$ structurally differs from another tree $t^*$ is a question that is encountered throughout computer science, including in understanding tree-structured data such as XML or JSON data. In this article, we explore how to learn explanations for structural differences between pairs of trees from sample data: suppose we are given a set $\{(t_1, t_1^*),\dots, (t_n, t_n^*)\}$ of pairs of labelled, ordered trees; is there a small set of rules that explains the structural differences between all pairs $(t_i, t_i^*)$? This raises two research questions: (i) what is a good notion of "rule" in this context?; and (ii) how can sets of rules explaining a data set be learnt algorithmically? We explore these questions from the perspective of database theory by (1) introducing a pattern-based specification language for tree transformations; (2) exploring the computational complexity of variants of the above algorithmic problem, e.g. showing NP-hardness for very restricted variants; and (3) discussing how to solve the problem for data from CS education research using SAT solvers.

We study the problem of learning linear temporal logic (LTL) formulas from examples, as a first step towards expressing a property separating positive and negative instances in a way that is comprehensible for humans. In this paper we initiate the study of the computational complexity of the problem. Our main results are hardness results: we show that the LTL learning problem is NP-complete, both for the full logic and for almost all of its fragments. This motivates the search for efficient heuristics, and highlights the complexity of expressing separating properties in concise natural language.

U.S. Army veteran Richard Neider is able to walk again after suffering a spinal-cord injury in Iraq thanks to a robotic exoskeleton. Neider, who is the first veteran in Phoenix to receive the ReWalk Personal 6.0 Exoskeleton through a Veterans Affairs program, was unable to walk after being injured in an explosion in Iraq and has spent almost ten years in a wheelchair. The battery-powered, motorized device has sensors that detect when he shifts his weight and then tells Neider's other leg to move - creating a walking motion. The light exoskeleton helps to stabilize his knees and hip. 'I can't ever stop smiling when I'm in it,' the former Army sergeant, who saw his May 2005 injury worsen over time, tells AZFamily.