We close affirmatively a question that has been open for long time: decidability of the HOM problem. The HOM problem consists in determining, given a tree homomorphism H and a regular tree language L represented by a tree automaton, whether H ( L ) is regular. In order to decide the HOM problem, we develop new constructions and techniques that are interesting by themselves, and provide several significant intermediate results. For example, we prove that the universality problem is decidable for languages represented by tree automata with equality constraints, and that the equivalence and inclusion problems are decidable for images of regular languages through tree homomorphisms. Our contributions are based on the following new constructions. We describe a simple transformation for converting a tree automaton with equality constraints into a tree automaton with disequality constraints recognizing the complementary language. We also define a new class of tree automata with arbitrary disequality constraints and a particular kind of equality constraints. An automaton of this new class essentially recognizes the intersection of a tree automaton with disequality constraints and the image of a regular language through a tree homomorphism. We prove decidability of emptiness and finiteness for this class by a pumping mechanism. We combine the above constructions adequately to provide an algorithm deciding the HOM problem. This is the journal version of a paper presented in the 42nd ACM Symposium on Theory of Computing (STOC 2010). Here, we provide all proofs and examples. Moreover, we obtain better complexity results via the modification of some proofs and a careful complexity analysis. In particular, the obtained time complexity for the decision of HOM is a tower of three exponentials.

Jutge.org is an open access educational online programming judge where students can try to solve more than 800 problems using 22 programming languages. The verdict of their solutions is computed using exhaustive test sets run under time, memory and security restrictions. By contrast to many popular online judges, Jutge.org is designed for students and instructors: On one hand, the problem repository is mainly aimed to beginners, with a clear organization and gradding. On the other hand, the system is designed as a virtual learning environment where instructors can administer their own courses, manage their roster of students and tutors, add problems, attach documents, create lists of problems, assignments, contests and exams. This paper presents Jutge.org and offers some case studies of courses using it.

Let Pn denote a graph drawn uniformly at random from the class of all simple planar graphs with n vertices. We show that the maximum degree of a vertex in Pn is with probability 1 − o(1) asymptotically equal to c log n, where c ≈ 2.529 is determined explicitly. A similar result is also true for random 2-connected planar graphs. Our analysis combines two orthogonal methods that complement each other. First, in order to obtain the upper bound, we resort to exact methods, i.e., to generating functions and analytic combinatorics. This allows us to obtain fairly precise asymptotic estimates for the expected number of vertices of any given degree in Pn. On the other hand, for the lower bound we use Boltzmann sampling. In particular, by tracing the execution of an adequate algorithm that generates a random planar graph, we are able to explicitly find vertices of sufficiently high degree in Pn.

Finite-state tree automata are a well-studied formalism for representing term languages. This paper studies the problem of determining the regularity of the set of instances of a finite set of terms with variables, where each variable is restricted to instantiations of a regular set given by a tree automaton. The problem was recently proved decidable, but with an unknown complexity. Here, the exact complexity of the problem is determined by proving EXPTIME-completeness. The main contribution is a new, exponential time algorithm that performs various exponential transformations on the involved terms and tree automata and decides regularity by analyzing formulas over inequation and height predicates.

We provide an algorithm that, given a tree homomorphism H and a regular tree language L represented by a tree automaton, determines whether H(L) is regular. This settles a question that has been open for a long time.

Recently, considerable focus has been given to the problem of determining the boundary between tractable and intractable planning problems. In this paper, we study the complexity of planning in the class C_n of planning problems, characterized by unary operators and directed path causal graphs. Although this is one of the simplest forms of causal graphs a planning problem can have, we show that planning is intractable for C_n (unless P = NP), even if the domains of state variables have bounded size. In particular, we show that plan existence for C_n^k is NP-hard for k>=5 by reduction from CNFSAT. Here, k denotes the upper bound on the size of the state variable domains. Our result reduces the complexity gap for the class C_n^k to cases k=3 and k=4 only, since C_n^2 is known to be tractable.

We present three new complexity results for classes of planning problems with simple causal graphs. First, we describe a polynomial-time algorithm that uses macros to generate plans for the class 3S of planning problems with binary state variables and acyclic causal graphs. This implies that plan generation may be tractable even when a planning problem has an exponentially long minimal solution. We also prove that the problem of plan existence for planning problems with multi-valued variables and chain causal graphs is NP-hard. Finally, we show that plan existence for planning problems with binary state variables and polytree causal graphs is NP-complete.

The Tutte polynomial is a notoriously hard graph invariant, and efficient algorithms for it are known only for a few special graph classes, like for those of bounded tree‐width. The notion of clique‐width extends the definition of cographs (graphs without induced $P_4$), and it is a more general notion than that of tree‐width. We show a subexponential algorithm (running in time $\exp{O(n^{1-\varepsilon})}\,$) for computing the Tutte polynomial on graphs of bounded clique‐width. In fact, our algorithm computes the more general U‐polynomial.