The Experts below are selected from a list of 54 Experts worldwide ranked by ideXlab platform

Santiago Figueira - One of the best experts on this subject based on the ideXlab platform.

  • Logics of repeating values on data trees and branching counter systems
    2017
    Co-Authors: Sergio Abriola, Diego Figueira, Santiago Figueira
    Abstract:

    We study connections between the satisfiability problem for logics on data trees and Branching Vector Addition Systems (BVAS). We consider a natural temporal logic of " repeating values " (LRV) featuring an operator which tests whether a data value in the current Node is repeated in some Descendant Node. On the one hand, we show that the satisfiability of a restricted version of LRV on ranked data trees can be reduced to the coverability problem for Branching Vector Addition Systems. This immediately gives elementary upper bounds for its satisfiability problem, showing that restricted LRV behaves much better than downward-XPath, which has a non-primitive-recursive satisfiability problem. On the other hand, satisfiability for LRV is shown to be reducible to the coverability for a novel branching model we introduce here, called Merging VASS (MVASS). MVASS is an extension of Branching Vector Addition Systems with States (BVASS) allowing richer merging operations of the vectors. We show that the control-state reachability for MVASS, as well as its bottom-up coverability, are in 3ExpTime. This work can be seen as a natural continuation of the work initiated by Demri, D'Souza and Gascon for the case of data words, this time considering branching structures and counter systems, although, as we show, in the case of data trees more powerful models are needed to encode satisfiability.

  • FoSSaCS - Logics of Repeating Values on Data Trees and Branching Counter Systems
    Lecture Notes in Computer Science, 2017
    Co-Authors: Sergio Abriola, Diego Figueira, Santiago Figueira
    Abstract:

    We study connections between the satisfiability problem for logics on data trees and Branching Vector Addition Systems BVAS. We consider a natural temporal logic of "repeating values" LRV featuring an operator which tests whether a data value in the current Node is repeated in some Descendant Node. On the one hand, we show that the satisfiability of a restricted version of LRV on ranked data trees can be reduced to the coverability problem for Branching Vector Addition Systems. This immediately gives elementary upper bounds for its satisfiability problem, showing that restricted LRV behaves much better than downward-XPath, which has a non-primitive-recursive satisfiability problem. On the other hand, satisfiability for LRV is shown to be reducible to the coverability for a novel branching model we introduce here, called Merging VASS MVASS. MVASS is an extension of Branching Vector Addition Systems with States BVASS allowing richer merging operations of the vectors. We show that the control-state reachability for MVASS, as well as its bottom-up coverability, are in 3ExpTime. This work can be seen as a natural continuation of the work initiated by Demri, D'Souza and Gascon for the case of data words, this time considering branching structures and counter systems, although, as we show, in the case of data trees more powerful models are needed to encode satisfiability.

Sergio Abriola - One of the best experts on this subject based on the ideXlab platform.

  • Logics of repeating values on data trees and branching counter systems
    2017
    Co-Authors: Sergio Abriola, Diego Figueira, Santiago Figueira
    Abstract:

    We study connections between the satisfiability problem for logics on data trees and Branching Vector Addition Systems (BVAS). We consider a natural temporal logic of " repeating values " (LRV) featuring an operator which tests whether a data value in the current Node is repeated in some Descendant Node. On the one hand, we show that the satisfiability of a restricted version of LRV on ranked data trees can be reduced to the coverability problem for Branching Vector Addition Systems. This immediately gives elementary upper bounds for its satisfiability problem, showing that restricted LRV behaves much better than downward-XPath, which has a non-primitive-recursive satisfiability problem. On the other hand, satisfiability for LRV is shown to be reducible to the coverability for a novel branching model we introduce here, called Merging VASS (MVASS). MVASS is an extension of Branching Vector Addition Systems with States (BVASS) allowing richer merging operations of the vectors. We show that the control-state reachability for MVASS, as well as its bottom-up coverability, are in 3ExpTime. This work can be seen as a natural continuation of the work initiated by Demri, D'Souza and Gascon for the case of data words, this time considering branching structures and counter systems, although, as we show, in the case of data trees more powerful models are needed to encode satisfiability.

  • FoSSaCS - Logics of Repeating Values on Data Trees and Branching Counter Systems
    Lecture Notes in Computer Science, 2017
    Co-Authors: Sergio Abriola, Diego Figueira, Santiago Figueira
    Abstract:

    We study connections between the satisfiability problem for logics on data trees and Branching Vector Addition Systems BVAS. We consider a natural temporal logic of "repeating values" LRV featuring an operator which tests whether a data value in the current Node is repeated in some Descendant Node. On the one hand, we show that the satisfiability of a restricted version of LRV on ranked data trees can be reduced to the coverability problem for Branching Vector Addition Systems. This immediately gives elementary upper bounds for its satisfiability problem, showing that restricted LRV behaves much better than downward-XPath, which has a non-primitive-recursive satisfiability problem. On the other hand, satisfiability for LRV is shown to be reducible to the coverability for a novel branching model we introduce here, called Merging VASS MVASS. MVASS is an extension of Branching Vector Addition Systems with States BVASS allowing richer merging operations of the vectors. We show that the control-state reachability for MVASS, as well as its bottom-up coverability, are in 3ExpTime. This work can be seen as a natural continuation of the work initiated by Demri, D'Souza and Gascon for the case of data words, this time considering branching structures and counter systems, although, as we show, in the case of data trees more powerful models are needed to encode satisfiability.

Wang Wei-hong - One of the best experts on this subject based on the ideXlab platform.

  • Structural Join Algorithm for XML/GML Non-spatial Data Querying
    Computer Engineering, 2010
    Co-Authors: Wang Wei-hong
    Abstract:

    In order to take advantage of Dewey prefix encoding scheme to encode eXtensible Markup Language(XML)/Geography Markup Language(GML) documents and eliminate Dewey encoding scheme’s shortcoming, a kind of extended Dewey encoding scheme, Ex-Dewey, is proposed. Ex-Dewey achieves updating strategy of Node’s inserting and deleting no affecting others’ encoding value, and also keeps the advantages of Dewey encoding scheme. And corresponding structural join algorithms, ED-XQ-SJ for XML or GML non-spatial data querying are proposed. The algorithms’ idea, description and verification are given. The algorithms can directly determine the ancestors-Descendants or parents-children relationship between potential ancestor Node set and Descendant Node set, and do not access the real storage Nodes. Their complexity is much reduced, and the I/O overhead is decreased obviously as well.

Diego Figueira - One of the best experts on this subject based on the ideXlab platform.

  • Logics of repeating values on data trees and branching counter systems
    2017
    Co-Authors: Sergio Abriola, Diego Figueira, Santiago Figueira
    Abstract:

    We study connections between the satisfiability problem for logics on data trees and Branching Vector Addition Systems (BVAS). We consider a natural temporal logic of " repeating values " (LRV) featuring an operator which tests whether a data value in the current Node is repeated in some Descendant Node. On the one hand, we show that the satisfiability of a restricted version of LRV on ranked data trees can be reduced to the coverability problem for Branching Vector Addition Systems. This immediately gives elementary upper bounds for its satisfiability problem, showing that restricted LRV behaves much better than downward-XPath, which has a non-primitive-recursive satisfiability problem. On the other hand, satisfiability for LRV is shown to be reducible to the coverability for a novel branching model we introduce here, called Merging VASS (MVASS). MVASS is an extension of Branching Vector Addition Systems with States (BVASS) allowing richer merging operations of the vectors. We show that the control-state reachability for MVASS, as well as its bottom-up coverability, are in 3ExpTime. This work can be seen as a natural continuation of the work initiated by Demri, D'Souza and Gascon for the case of data words, this time considering branching structures and counter systems, although, as we show, in the case of data trees more powerful models are needed to encode satisfiability.

  • FoSSaCS - Logics of Repeating Values on Data Trees and Branching Counter Systems
    Lecture Notes in Computer Science, 2017
    Co-Authors: Sergio Abriola, Diego Figueira, Santiago Figueira
    Abstract:

    We study connections between the satisfiability problem for logics on data trees and Branching Vector Addition Systems BVAS. We consider a natural temporal logic of "repeating values" LRV featuring an operator which tests whether a data value in the current Node is repeated in some Descendant Node. On the one hand, we show that the satisfiability of a restricted version of LRV on ranked data trees can be reduced to the coverability problem for Branching Vector Addition Systems. This immediately gives elementary upper bounds for its satisfiability problem, showing that restricted LRV behaves much better than downward-XPath, which has a non-primitive-recursive satisfiability problem. On the other hand, satisfiability for LRV is shown to be reducible to the coverability for a novel branching model we introduce here, called Merging VASS MVASS. MVASS is an extension of Branching Vector Addition Systems with States BVASS allowing richer merging operations of the vectors. We show that the control-state reachability for MVASS, as well as its bottom-up coverability, are in 3ExpTime. This work can be seen as a natural continuation of the work initiated by Demri, D'Souza and Gascon for the case of data words, this time considering branching structures and counter systems, although, as we show, in the case of data trees more powerful models are needed to encode satisfiability.

Georgios K. D. Saharidis - One of the best experts on this subject based on the ideXlab platform.

  • Benders decomposition with integer subproblem
    Expert Systems with Applications, 2017
    Co-Authors: Ashkan Fakhri, Mehdi Ghatee, Antonios Fragkogios, Georgios K. D. Saharidis
    Abstract:

    A Branch-and-Cut algorithm using Benders decomposition method is proposed.The algorithm is applied in case of integer subproblem.Local and Global Cuts are used to warm start the master problem in each Node.The validity of the cuts is mathematically proved.A case study tests the efficiency of the algorithm. The application of Benders decomposition method to a problem might result in a subproblem including integer variables. In this case, it is not able to apply the classical Benders algorithm. In this study we present a Branch-and-Cut algorithm, which introduces the notion of Local Cuts as well as Global Cuts. The integrality constraints of the subproblem are relaxed and the relaxed problem is solved in a branch-and-bound framework, where in each Node, the Benders algorithm is applied between the master problem and the relaxed subproblem. Benders cuts generated in a Node of the branch-and bound tree are proved to be valid for all its Descendants, but they are not necessarily valid for the non-Descendant Nodes. These cuts, referred to as local cuts, can be used to warm start the master problem of each Descendant Node, thus leading to better initial bounds. Furthermore, a novel way is presented for defining the local cuts in a general form. This general form is in fact a function of the subproblems variables and enables us to reuse the generated (local) cuts in the whole tree by updating some values of the function. The performance of the proposed algorithm is tested on the classical Capacitated Fixed Charge Multiple Knapsack Problem (CFCMKP).