Library

X
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
    Sufficient-completeness, ground-reducibility and their complexity (1992)
    Springer
    International journal of biometeorology 36 (1992), S. 311-350 
    Details
    ISSN: 1432-1254
    Source: Springer Online Journal Archives 1860-2000
    Topics: Geography , Physics
    Notes: Summary The sufficient-completeness property of equational algebraic specifications has been found useful in providing guidelines for designing abstract data type specifications as well as in proving inductive properties using the induction-less-induction method. The sufficient-completeness property is known to be undecidable in general. In an earlier paper, it was shown to be decidable for constructor-preserving, complete (canonical) term rewriting systems, even when there are relations among constructor symbols. In this paper, the complexity of the sufficient-completeness property is analyzed for different classes of term rewriting systems. A number of results about the complexity of the sufficient-completeness property for complete (canonical) term rewriting systems are proved: (i) The problem is co-NP-complete for term rewriting systems with free constructors (i.e., no relations among constructors are allowed), (ii) the problem remains co-NP-complete for term rewriting systems with unary and nullary constructors, even when there are relations among constructors, (iii) the problem is provably in “almost” exponential time for left-linear term rewriting systems with relations among constructors, and (iv) for left-linear complete constructor-preserving rewriting systems, the problem can be decided in steps exponential innlogn wheren is the size of the rewriting system. No better lower-bound for the complexity of the sufficient-completeness property for complete (canonical) term rewriting system with nonlinear left-hand sides is known. An algorithm for left-linear complete constructor-preserving rewriting systems is also discussed. Finally, the sufficient-completeness property is shown to be undecidable for non-linear complete term rewriting systems with associative functions. These complexity results also apply to the ground-reducibility property (also called inductive-reducibility) which is known to be directly related to the sufficient-completeness property.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01212959
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Facility Dispersion Problems Under Capacity and Cost Constraints (2000)
    Springer
    Journal of combinatorial optimization 4 (2000), S. 7-33 
    Details
    ISSN: 1573-2886
    Keywords: dispersion ; storage capacity ; storage cost ; optimization ; polynomial algorithm ; approximation scheme
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The MAX-MIN dispersion problem, which arises in the placement of undesirable facilities, involves selecting a specified number of sites among a set of potential sites so as to maximize the minimum distance between any pair of selected sites. We consider different versions of this dispersion problem where each potential site has an associated storage capacity and a storage cost. A typical problem in this context is to choose a subset of potential sites so that the total capacity of the chosen sites is at least a given value, the total storage cost is within the specified budget and the minimum distance between any pair of chosen sites is maximized. Since these constrained optimization problems are NP-hard in general, we consider whether there are efficient approximation algorithms for them with good performance guarantees. Our results include approximation algorithms for some versions, approximation schemes for some geometric versions and polynomial algorithms for special cases. We also present results that bring out the intrinsic difficulty of obtaining near-optimal solutions to some versions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1009802105661
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Using Data Flow Information to Obtain Efficient Check Sets for Algorithm-Based Fault Tolerance (1999)
    Springer
    International journal of parallel programming 27 (1999), S. 289-323 
    Details
    ISSN: 1573-7640
    Keywords: MULTIPROCESSOR ; DATA FLOW ; FAULT DETECTION ; FAULT LOCATION ; ALGORITHMS
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Algorithm-Based Fault Tolerance (ABFT) is a well known technique for achieving fault and error detection in multiprocessor systems. We examine several issues concerning ABFT systems when the data flow information for the underlying multiprocessor computation is available. Our results show that this finergrained information can be exploited to obtain test schemes involving fewer checks, in some cases, dramatically fewer checks. We address both the analysis and design of ABFT systems when the data flow information is available. The analysis problem for a given ABFT system is to determine the fault detectability and the fault locatability (maximum number of detectable and locatable faulty processors) of the system. We show that the analysis problem can be solved efficiently when the number of faults is fixed. We also address the computational difficulty of this problem when the number of faults is not fixed. The design problem is concerned with the construction of a minimal collection of checks which can detect or locate a specified number of faults for a given multiprocessor computation. We examine some special classes of data flow graphs and establish upper and lower bounds on the number of checks needed to detect or locate a given number of faults. We also address the computational difficulty of this design problem for several cases.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1018793714426
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Sufficient-completeness, ground-reducibility and their complexity (1991)
    Springer
    Acta informatica 28 (1991), S. 311-350 
    Details
    ISSN: 1432-0525
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary The sufficient-completeness property of equational algebraic specifications has been found useful in providing guidelines for designing abstract data type specifications as well as in proving inductive properties using the induction-less-induction method. The sufficient-completeness property is known to be undecidable in general. In an earlier paper, it was shown to be decidable for constructor-preserving, complete (canonical) term rewriting systems, even when there are relations among constructor symbols. In this paper, the complexity of the sufficient-completeness property is analyzed for different classes of term rewriting systems. A number of results about the complexity of the sufficient-completeness property for complete (canonical) term rewriting systems are proved: (i) The problem is co-NP-complete for term rewriting systems with free constructors (i.e., no relations among constructors are allowed), (ii) the problem remains co-NP-complete for term rewriting systems with unary and nullary constructors, even when there are relations among constructors, (iii) the problem is provably in “almost” exponential time for left-linear term rewriting systems with relations among constructors, and (iv) for left-linear complete constructor-preserving rewriting systems, the problem can be decided in steps exponential innlogn wheren is the size of the rewriting system. No better lower-bound for the complexity of the sufficient-completeness property for complete (canonical) term rewriting system with nonlinear left-hand sides is known. An algorithm for left-linear complete constructor-preserving rewriting systems is also discussed. Finally, the sufficient-completeness property is shown to be undecidable for non-linear complete term rewriting systems with associative functions. These complexity results also apply to the ground-reducibility property (also called inductive-reducibility) which is known to be directly related to the sufficient-completeness property.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01893885
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Minimizing time-space cost for database version control (1990)
    Springer
    Acta informatica 27 (1990), S. 627-663 
    Details
    ISSN: 1432-0525
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary We introduce the concept of a version graph to model the problem of minimizing the combined cost of storage space and version regeneration time for database version control systems. We show that, in general, this problem and several of its variations are NP-complete. Several heuristics are developed, and performance guarantees for these heuristics are obtained. We also present linear time algorithms for special classes of version graphs; these special classes are likely to apply in many version control systems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00259470
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...