Search results for " programmi"
showing 10 items of 1629 documents
On the Power of Tree-Walking Automata
2000
Tree-walking automata (TWAs) recently received new attention in the fields of formal languages and databases. Towards a better understanding of their expressiveness, we characterize them in terms of transitive closure logic formulas in normal form. It is conjectured by Engelfriet and Hoogeboom that TWAs cannot define all regular tree languages, or equivalently, all of monadic second-order logic. We prove this conjecture for a restricted, but powerful, class of TWAs. In particular, we show that 1-bounded TWAs, that is TWAs that are only allowed to traverse every edge of the input tree at most once in every direction, cannot define all regular languages. We then extend this result to a class …
Polyhedral results for a vehicle routing problem
1991
Abstract The Vehicle Routing Problem is a well known, and hard, combinatorial problem, whose polyhedral structure has deserved little attention. In this paper we consider the particular case in which all the demands are equal (since in the general case the associated polytope may be empty). From a known formulation of the problem we obtain the dimension of the corresponding polytope and we study the facetial properties of every inequality in it.
Nondeterministic operations on finite relational structures
1998
Abstract This article builds on a tutorial introduction to universal algebra for language theory (Courcelle, Theoret. Comput. Sci. 163 (1996) 1–54) and extends it in two directions. First, nondeterministic operations are considered, i.e., operations which give a set of results instead of a single one. Most of their properties concerning recognizability and equational definability carry over from the ordinary case with minor modifications. Second, inductive sets of evaluations are studied in greater detail. It seems that they are handled most naturally in the framework presented here. We consider the analogues of top-down and bottom-up tree transducers. Again, most of their closure propertie…
Branch and bound for the cutwidth minimization problem
2013
The cutwidth minimization problem consists of finding a linear arrangement of the vertices of a graph where the maximum number of cuts between the edges of the graph and a line separating consecutive vertices is minimized. We first review previous approaches for special classes of graphs, followed by lower bounds and then a linear integer formulation for the general problem. We then propose a branch-and-bound algorithm based on different lower bounds on the cutwidth of partial solutions. Additionally, we introduce a Greedy Randomized Adaptive Search Procedure (GRASP) heuristic to obtain good initial solutions. The combination of the branch-and-bound and GRASP methods results in optimal solu…
Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem
2014
The bipartite unconstrained 0-1 quadratic programming problem (BQP) is a difficult combinatorial problem defined on a complete graph that consists of selecting a subgraph that maximizes the sum of the weights associated with the chosen vertices and the edges that connect them. The problem has appeared under several different names in the literature, including maximum weight induced subgraph, maximum weight biclique, matrix factorization and maximum cut on bipartite graphs. There are only two unpublished works (technical reports) where heuristic approaches are tested on BQP instances. Our goal is to combine straightforward search elements to balance diversification and intensification in bot…
The Asynchronous Leontief Model
1992
International audience; The traditional dynamic Leontief model is synchronous: every vertex acts simultaneously. A model with delays of action has been proposed, but it still remains synchronous. In this paper we propose an asynchronous version of the model that allows realistic computations. We fiurnish an algorithm and a program.
On the best Lipschitz extension problem for a discrete distance and the discrete ∞-Laplacian
2012
Abstract This paper concerns the best Lipschitz extension problem for a discrete distance that counts the number of steps. We relate this absolutely minimizing Lipschitz extension with a discrete ∞-Laplacian problem, which arises as the dynamic programming formula for the value function of some e -tug-of-war games. As in the classical case, we obtain the absolutely minimizing Lipschitz extension of a datum f by taking the limit as p → ∞ in a nonlocal p -Laplacian problem.
On generalized a-Browder's theorem
2007
We characterize the bounded linear operators T satisfying generalized a-Browder's theorem, or generalized a-Weyl's theorem, by means of localized SVEP, as well as by means of the quasi-nilpotent part H0(�I T) asbelongs to certain sets of C. In the last part we give a general framework in which generalized a-Weyl's theorem follows for several classes of operators. 1. Preliminaries. Let L(X) denote the space of bounded linear oper- ators on an infinite-dimensional complex Banach space X. For T ∈ L(X), denote by α(T) the dimension of the kernel ker T, and by β(T) the codi- mension of the range T(X). The operator T ∈ L(X) is called upper semi- Fredholm if α(T) < ∞ and T(X) is closed, and lower …
Nonlinear systems solver in floating-point arithmetic using LP reduction
2009
This paper presents a new solver for systems of nonlinear equations. Such systems occur in Geometric Constraint Solving, e.g., when dimensioning parts in CAD-CAM, or when computing the topology of sets defined by nonlinear inequalities. The paper does not consider the problem of decomposing the system and assembling solutions of subsystems. It focuses on the numerical resolution of well-constrained systems. Instead of computing an exponential number of coefficients in the tensorial Bernstein basis, we resort to linear programming for computing range bounds of system equations or domain reductions of system variables. Linear programming is performed on a so called Bernstein polytope: though,…
On the Bishop–Phelps–Bollobás theorem for multilinear mappings
2017
Abstract We study the Bishop–Phelps–Bollobas property and the Bishop–Phelps–Bollobas property for numerical radius. Our main aim is to extend some known results about norm or numerical radius attaining operators to multilinear and polynomial cases. We characterize the pair ( l 1 ( X ) , Y ) to have the BPBp for bilinear forms and prove that on L 1 ( μ ) the numerical radius and the norm of a multilinear mapping are the same. We also show that L 1 ( μ ) fails the BPBp-nu for multilinear mappings although L 1 ( μ ) satisfies it in the operator case for every measure μ.