Real-world manufacturing scenarios usually lead to difficult assembly scheduling problems.Besides strict precedence constraints between jobs or operations, such problems incorporate constraints related to maintenance activities on working stations (machines) and specific setup times when different operations are executed on the same machine.This paper analyzes the performance of several approaches, based on mathematical programming and on (meta)heuristics, to solve flexible assembly scheduling problems characterized by an arbitrary tree-like structure of the operation network.In this context, a specific encoding of candidate solutions and some specific perturbation operators are proposed.The encoding and the operators allow the distribution of sub(batches) of operations on several machines which leads, for some assembly scheduling problems, to a significant decrease of the makespan.

We study the matching problem of regular tree languages, that is, "$\exists \sigma:\sigma(L)\subseteq R$?" where $L,R$ are regular tree languages over the union of finite ranked alphabets $\Sigma$ and $\mathcal{X}$ where $\mathcal{X}$ is an alphabet of variables and $\sigma$ is a substitution such that $\sigma(x)$ is a set of trees in $T(\Sigma\cup H)\setminus H$ for all $x\in \mathcal{X}$. Here, $H$ denotes a set of "holes" which are used to define a "sorted" concatenation of trees. Conway studied this problem in the special case for languages of finite words in his classical textbook "Regular algebra and finite machines" published in 1971. He showed that if $L$ and $R$ are regular, then the problem "$\exists \sigma \forall x\in \mathcal{X}: \sigma(x)\neq \emptyset\wedge \sigma(L)\subseteq R$?" is decidable. Moreover, there are only finitely many maximal solutions, the maximal solutions are regular substitutions, and they are effectively computable. We extend Conway's results when $L,R$ are regular languages of finite and infinite trees, and language substitution is applied inside-out, in the sense of Engelfriet and Schmidt (1977/78). More precisely, we show that if $L\subseteq T(\Sigma\cup\mathcal{X})$ and $R\subseteq T(\Sigma)$ are regular tree languages over finite or infinite trees, then the problem "$\exists \sigma \forall x\in \mathcal{X}: \sigma(x)\neq \emptyset\wedge \sigma_{\mathrm{io}}(L)\subseteq R$?" is decidable. Here, the subscript "$\mathrm{io}$" in $\sigma_{\mathrm{io}}(L)$ refers to "inside-out". Moreover, there are only finitely many maximal solutions $\sigma$, the maximal solutions are regular substitutions and effectively computable. The corresponding question for the outside-in extension $\sigma_{\mathrm{oi}}$ remains open, even in the restricted setting of finite trees.

In this paper we study matching in equational theories that specify counterparts of associativity and commutativity for variadic function symbols. We design a procedure to solve a system of matching equations and prove its termination, soundness, completeness, and minimality. The minimal complete set of matchers for such a system can be infinite, but our algorithm computes its finite representation in the form of solved set. From the practical side, we identify two finitary cases and impose restrictions on the procedure to get an incomplete algorithm, which, based on our experiments, describes the input-output behavior and properties of Mathematica's flat and orderless pattern matching.

Similarity relations are reflexive, symmetric, and transitive fuzzy relations. They help to make approximate inferences, replacing the notion of equality. Similarity-based unification has been quite intensively investigated, as a core computational method for approximate reasoning and declarative programming. In this paper we consider solving constraints over several similarity relations, instead of a single one. Multiple similarities pose challenges to constraint solving, since we can not rely on the transitivity property anymore. Existing methods for unification with fuzzy proximity relations (reflexive, symmetric, non-transitive relations) do not provide a solution that would adequately reflect particularities of dealing with multiple similarities. To address this problem, we develop a constraint solving algorithm for multiple similarity relations, prove its termination, soundness, and completeness properties, and discuss applications.

ABACα is a foundational model for attribute-based access control with a minimal set of capabilities to configure many access control models of interest, including the dominant traditional ones: discretionary (DAC), mandatory (MAC), and role-based (RBAC). A fundamental security problem in the design of ABAC is to ensure safety, that is, to guarantee that a certain subject can never gain certain permissions to access certain object(s).

Abstract CLP(H) is an instantiation of the general constraint logic programming scheme with the constraint domain of hedges. Hedges are finite sequences of unranked terms, built over variadic function symbols and three kinds of variables: for terms, for hedges, and for function symbols. Constraints involve equations between unranked terms and atoms for regular hedge language membership. We study algebraic semantics of CLP(H) programs, define a sound, terminating, and incomplete constraint solver, investigate two fragments of constraints for which the solver returns a complete set of solutions, and describe classes of programs that generate such constraints.

We extend order-sorted unification by permitting regular expression sorts for variables and in the domains of function symbols. The obtained signature corresponds to a finite bottom-up unranked tree automaton. We prove that regular expression order-sorted (REOS) unification is of type infinitary and decidable. The unification problem presented by us generalizes some known problems, such as, e.g., order-sorted unification for ranked terms, sequence unification, and word unification with regular constraints. Decidability of REOS unification implies that sequence unification with regular hedge language constraints is decidable, generalizing the decidability result of word unification with regular constraints to terms. A sort weakening algorithm helps to construct a minimal complete set of REOS unifiers from the solutions of sequence unification problems. Moreover, we design a complete algorithm for REOS matching, and show that this problem is NP-complete and the corresponding counting problem is #P-complete.

We extend first-order order-sorted unification by permitting regular expression sorts for variables and in the domains of function symbols. The set of basic sorts is finite. The obtained signature corresponds to a finite bottom-up hedge automaton. The unification problem in such a theory generalizes some known unification problems. Its unification type is infinitary. We give a complete unification procedure and prove decidability.

We show the completeness of the lazy conditional narrowing calculus (LCNC) with leftmost selection for the class of deterministic conditional rewrite systems (CTRSs). Deterministic CTRSs permit extra variables in the right-hand sides and conditions of their rewrite rules. From the completeness proof we obtain several insights to make the calculus more deterministic. Furthermore, and similar to the refinements developed for the unconditional case, we succeeded in removing all nondeterminism due to the choice of the inference rule of LCNC by imposing further syntactic conditions on the participating CTRSs and restricting the set of solutions for which completeness needs to be established.