Erschienen in:

1985 | ReviewPaper | Buchkapitel

From domino tilings to a new model of computation

verfasst von : Bogdan S. Chlebus

Erschienen in: Computation Theory

Verlag: Springer Berlin Heidelberg

Enthalten in: Professional Book Archive

Zugang erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

A new model of computation called VH-system is introduced. It is a formalization of domino tilings. We show how the semantics of nondeterminism on VH-systems, being a natural counterpart of the machinery of tilings, can be modified to cover both deterministic and alternating computations. As a by-product we present a new proof of the fact that the satisfiability problem of boolean Horn formulas is complete in PTIME.

Springer Professional