Search

Abstract In this paper, the problem of tree size reduction with guarantee of preserving distinguishability is studied. Given a query q and a tree T , evaluating q on T will output q (T) which is a set of nodes of T. Given two nodes a and b in T , they are said to be distinguished by some query q in T , iff exactly one of them belongs to q (T). Then, given a tree T , a query class L , and two disjoint node sets A and B of T , a subtree T ′ of T satisfies the condition of preserving distinguishability of T , iff (1) T ′ contains all nodes in A ∪ B , (2) for any node pair (a , b) ∈ A × B , if a and b can be distinguished by some query in L in T , they can also be distinguished by some query (not necessarily the same one) in L in T ′ , and (3) for any node pair (a , b) ∈ A × B and a query q ∈ L , if a and b can be distinguished by q in T ′ , they can also be distinguished by q in T. The tree size reduction problem considered by this paper is to determine whether there is a small enough subtree T ′ of T , such that for query class L and node sets A and B , T ′ preserves the distinguishability of T. In this paper, as an initial attempt of investigating this problem, fixing L to be a specific part of tree pattern queries which is an important practical query language on trees, the tree size reduction problem is shown to be NP- complete. [ABSTRACT FROM AUTHOR]

We give a new deterministic algorithm that non-adaptively learns a hidden hypergraph from edge-detecting queries. All previous non-adaptive algorithms either run in exponential time or have non-optimal query complexity. We give the first polynomial time non-adaptive learning algorithm for learning hypergraphs that asks an almost optimal number of queries. [ABSTRACT FROM AUTHOR]

The test specification language FQL describes relevant test goals as regular expressions over program locations, such that each matching test case has an execution path matching this expression. To specify not only test goals but entire suites, FQL describes families of related test goals by regular expressions over extended alphabets: Herein, each symbol corresponds to a regular expression over program locations, and thus, a word in an FQL expression corresponds to a regular expression describing a single test goal. In this paper we provide a systematic foundation for FQL test specifications, which are in fact rational sets of regular languages (RSRLs). To address practically relevant problems like query optimization, we tackle open questions about RSRLs: We settle closure properties of general and finite RSRLs under common set theoretic operations. We also prove complexity results for checking equivalence and inclusion of star-free RSRLs, and for deciding whether a regular language is a member of a general or star-free RSRL. [ABSTRACT FROM AUTHOR]