ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    Springer
    Constraints 5 (2000), S. 7-41 
    ISSN: 1572-9354
    Keywords: feature constraints ; tree orderings ; weak subsumption ; satisfiability ; entailment ; complexity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Feature trees are the formal basis for algorithms manipulating record like structures in constraint programming, computational linguistics and in concrete applications like software configuration management. Feature trees model records, and constraints over feature trees yield extensible and modular record descriptions. We introduce the constraint system FT≤ of ordering constraints interpreted over feature trees. Under the view that feature trees represent symbolic information, the relation ≤ corresponds to the information ordering (“carries less information than”). We present two algorithms in cubic time, one for the satisfiability problem and one for the entailment problem of FT≤. We show that FT≤ has the independence property. We are thus able to handle negative conjuncts via entailment and obtain a cubic algorithm that decides the satisfiability of conjunctions of positive and negated ordering constraints over feature trees. Furthermore, we reduce the satisfiability problem of Dörre's weak subsumption constraints to the satisfiability problem of FT≤ and improve the complexity bound for solving weak subsumption constraints from O(n5) to O(n3) .
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 2
    Electronic Resource
    Electronic Resource
    Springer
    Grammars 3 (2000), S. 217-241 
    ISSN: 1572-848X
    Keywords: constraints ; natural language semantics ; reinterpretation ; tree descriptions ; underspecification
    Source: Springer Online Journal Archives 1860-2000
    Topics: Linguistics and Literary Studies , Computer Science
    Notes: Abstract Type and sort conflicts in semantics are usually resolved by a process of reinterpretation, which introduces an operator into the semantic representation. We elaborate on the foundations of a recent approach to reinterpretation within a framework for semantic underspecification. In this approach, relaxed underspecified semantic representations are inferred from the syntactic structure, leaving space for subsequent addition of reinterpretation operators. Unfortunately, a structural danger of overgeneration is inherent to the relaxation of underspecified semantic representations. We identify the problem and distinguish structural properties that avoid it. We furthermore develop techniques for proving these properties and apply them to prove the safety of relaxation in a prototypical syntax/semantics interface. In doing so, we present some novel properties of tree descriptions in the constraint language over lambda structures (CLLS).
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 3
    Publication Date: 2006-08-16
    Print ISSN: 0885-6125
    Electronic ISSN: 1573-0565
    Topics: Computer Science
    Published by Springer
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 4
    Publication Date: 2017-03-10
    Electronic ISSN: 2079-3197
    Topics: Electrical Engineering, Measurement and Control Technology , Computer Science
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 5
    Publication Date: 2021-02-24
    Description: We consider the problem of determinizing and minimizing automata for nested words in practice. For this we compile the nested regular expressions (NREs) from the usual XPath benchmark to nested word automata (NWAs). The determinization of these NWAs, however, fails to produce reasonably small automata. In the best case, huge deterministic NWAs are produced after few hours, even for relatively small NREs of the benchmark. We propose a different approach to the determinization of automata for nested words. For this, we introduce stepwise hedge automata (SHAs) that generalize naturally on both (stepwise) tree automata and on finite word automata. We then show how to determinize SHAs, yielding reasonably small deterministic automata for the NREs from the XPath benchmark. The size of deterministic SHAs automata can be reduced further by a novel minimization algorithm for a subclass of SHAs. In order to understand why the new approach to determinization and minimization works so nicely, we investigate the relationship between NWAs and SHAs further. Clearly, deterministic SHAs can be compiled to deterministic NWAs in linear time, and conversely NWAs can be compiled to nondeterministic SHAs in polynomial time. Therefore, we can use SHAs as intermediates for determinizing NWAs, while avoiding the huge size increase with the usual determinization algorithm for NWAs. Notably, the NWAs obtained from the SHAs perform bottom-up and left-to-right computations only, but no top-down computations. This NWA behavior can be distinguished syntactically by the (weak) single-entry property, suggesting a close relationship between SHAs and single-entry NWAs. In particular, it turns out that the usual determinization algorithm for NWAs behaves well for single-entry NWAs, while it quickly explodes without the single-entry property. Furthermore, it is known that the class of deterministic multi-module single-entry NWAs enjoys unique minimization. The subclass of deterministic SHAs to which our novel minimization algorithm applies is different though, in that we do not impose multiple modules. As further optimizations for reducing the sizes of the constructed SHAs, we propose schema-based cleaning and symbolic representations based on apply-else rules that can be maintained by determinization. We implemented the optimizations and report the experimental results for the automata constructed for the XPathMark benchmark.
    Electronic ISSN: 1999-4893
    Topics: Computer Science
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 6
    Publication Date: 2021-10-21
    Description: We study the problem of how to compute the boolean abstraction of the solution set of a linear equation system over the positive reals. We call a linear equation system ϕ exact for the boolean abstraction if the abstract interpretation of ϕ over the structure of booleans is equal to the boolean abstraction of the solution set of ϕ over the positive reals. Abstract interpretation over the booleans is thus complete for the boolean abstraction when restricted to exact linear equation systems, while it is not complete more generally. We present a new rewriting algorithm that makes linear equation systems exact for the boolean abstraction while preserving the solutions over the positive reals. The rewriting algorithm is based on the elementary modes of the linear equation system. The computation of the elementary modes may require exponential time in the worst case, but is often feasible in practice with freely available tools. For exact linear equation systems, we can compute the boolean abstraction by finite domain constraint programming. This yields a solution of the initial problem that is often feasible in practice. Our exact rewriting algorithm has two further applications. Firstly, it can be used to compute the sign abstraction of linear equation systems over the reals, as needed for analyzing function programs with linear arithmetics. Secondly, it can be applied to compute the difference abstraction of a linear equation system as used in change prediction algorithms for flux networks in systems biology.
    Electronic ISSN: 2079-3197
    Topics: Electrical Engineering, Measurement and Control Technology , Computer Science
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...