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
    Bioinformatik (1999)
    Springer
    Informatik-Spektrum 22 (1999), S. 376-378 
    Details
    ISSN: 1432-122X
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s002870050166
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Cutting planes, connectivity, and threshold logic (1996)
    Springer
    Archive for mathematical logic 35 (1996), S. 33-62 
    Details
    ISSN: 1432-0665
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract. Originating from work in operations research the cutting plane refutation system $CP$ is an extension of resolution, where unsatisfiable propositional logic formulas in conjunctive normal form are recognized by showing the non-existence of boolean solutions to associated families of linear inequalities. Polynomial size $CP$ proofs are given for the undirected $s$ - $t$ connectivity principle. The subsystems $CP_q$ of $CP$ , for $q\ge 2$ , are shown to be polynomially equivalent to $CP$ , thus answering problem 19 from the list of open problems of [8]. We present a normal form theorem for $CP_2$ -proofs and thereby for arbitrary $CP$ -proofs. As a corollary, we show that the coefficients and constant terms in arbitrary cutting plane proofs may be exponentially bounded by the number of steps in the proof, at the cost of an at most polynomial increase in the number of steps in the proof. The extension $CPLE^+$ , introduced in [9] and there shown to $p$ -simulate Frege systems, is proved to be polynomially equivalent to Frege systems. Lastly, since linear inequalities are related to threshold gates, we introduce a new threshold logic and prove a completeness theorem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01845704
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Optimal bounds for ordinal comparison maps (1985)
    Springer
    Archive for mathematical logic 25 (1985), S. 99-107 
    Details
    ISSN: 1432-0665
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In this note, we answer the following question: Given two recursively presented well orderingsR, S of subsets of the natural numbers, what is the complexity of an ordinal comparison mapκ takingR isomorphically onto an initial segment ofS (or vice versa)?
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02007560
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Cutting planes, connectivity, and threshold logic (1996)
    Springer
    Archive for mathematical logic 35 (1996), S. 33-62 
    Details
    ISSN: 1432-0665
    Keywords: 03B05 ; 03F07 ; 03F20 ; 90C10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Originating from work in operations research the cutting plane refutation systemCP is an extension of resolution, where unsatisfiable propositional logic formulas in conjunctive normal form are recognized by showing the non-existence of boolean solutions to associated families of linear inequalities. Polynomial sizeCP proofs are given for the undirecteds-t connectivity principle. The subsystemsCP q ofCP, forq≥2, are shown to be polynomially equivalent toCP, thus answering problem 19 from the list of open problems of [8]. We present a normal form theorem forCP 2-proofs and thereby for arbitraryCP-proofs. As a corollary, we show that the coefficients and constant terms in arbitrary cutting plane proofs may be exponentially bounded by the number of steps in the proof, at the cost of an at most polynomial increase in the number of steps in the proof. The extensionCPLE +, introduced in [9] and there shown top-simulate Frege systems, is proved to be polynomially equivalent to Frege systems. Lastly, since linear inequalities are related to threshold gates, we introduce a new threshold logic and prove a completeness theorem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01845704
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    ALOGTIME and a conjecture of S.A. Cook (1992)
    Springer
    Annals of mathematics and artificial intelligence 6 (1992), S. 57-106 
    Details
    ISSN: 1573-7470
    Keywords: Frege proofs ; propositional calculus ; parallel complexity ; NC, free variable equational logic ; resolution proof
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Usingsequential, machine-independent characterization of theparallel complexity classesAC k andNC k , we establish the following conjecture of S.A. Cook. There is a free variable equational logicALV with the property thatif f, g are function symbols forALOGTIME computable functions for which “f=g” is provable inALV, then there are polynomial size Frege proofs for the infinite family {|f=g| m n :n, m∈ℕ} of propositional tautologies. Here, the propositional formula |f=g| m n expresses the equality off andg on inputs of length at mostn, provided that the function values are of length at mostm. We establish a related result with constant formula-depth polynomial size Frege proofs for a systemAV related to uniformAC 0 functions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01531023
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Book
    Book
    Computational molecular biology : an introduction (2000)
    Chichester [u.a.] :Wiley,
    Details
    Title: Computational molecular biology : an introduction
    Author: Clote, Peter
    Contributer: Backofen, Rolf
    Edition: 1
    Publisher: Chichester [u.a.] :Wiley,
    Year of publication: 2000
    Pages: IX, 286 S.
    Series Statement: Wiley series in mathematical and computational biology
    ISBN: 0-471-87252-0
    Type of Medium: Book
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    ZIB Catalog
    Zuse Institute Berlin get availability status
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...