ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

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
Filter
  • Articles  (2)
  • 1975-1979  (2)
Collection
  • Articles  (2)
Source
Keywords
Publisher
Years
Year
Topic
  • 1
    Electronic Resource
    Electronic Resource
    Space bounds for a game on graphs (1976)
    Springer
    Theory of computing systems 10 (1976), S. 239-251 
    Details
    ISSN: 1433-0490
    Keywords: Pebble game ; Register allocation ; Space bounds ; Turing machines
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We study a one-person game played by placing pebbles, according to certain rules, on the vertices of a directed graph. In [3] it was shown that for each graph withn vertices and maximum in-degreed, there is a pebbling strategy which requires at mostc(d) n/logn pebbles. Here we show that this bound is tight to within a constant factor. We also analyze a variety of pebbling algorithms, including one which achieves the 0(n/logn) bound.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01683275
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Boolesche Minimalpolynome und Überdeckungsprobleme (1975)
    Springer
    Acta informatica 4 (1975), S. 321-336 
    Details
    ISSN: 1432-0525
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary The main difficulty in finding minimal Boolean polynomials for given switching functions comes from the evaluation of the table of prime implicants. We show the following results: 1) Switching functions with “don't care”-points and those without yield essentially the same class of tables of prime implicants. 2) A polynomial, which is minimal with respect to the costfunction, which counts the entries of conjunctions and disjunctions, must not be a polynomial with a minimal number of prime implicants. 3) Each binary matrix with at least one 1 in each row and column is the prime implicant table of some switching-function. Moreover this function can be constructed such that its prime implicants have arbitrarily prescribed costs. Finally we make some remarks about the complexity of algorithms, which—given the graph of a switching function—find a minimal polynomial of this function.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00289615
    Location Call Number Expected 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...