From domino tilings to a new model of computation

Bogdan S. Chlebus(corresponding author)

*Corresponding author for this work

University of Warsaw

Scholary Output:

Chapter in Book/Report/Conference proceeding

Conference contribution

Related Event

Title

5th Symposium on Computation Theory, SCT 1984

Event type

Conference

Date

12/03/1984 - 12/08/1984

Location

ZaborowPoland

Abstract

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.

Publication Information

Output type

Scholary Output:

Chapter in Book/Report/Conference proceeding

Conference contribution

Original language

English (US)

Pages from-to (Number of pages)

Pages 24-33 (10 pages)

Publication milestones

Published - 01/01/1985

Publication status

Published - 01/01/1985

Publisher

Springer Verlag

Publication series

Publication series name: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print): 0302-9743
ISSN (Electronic): 1611-3349
Volume: 208 LNCS

ISBN (Print)

9783540160663

Publication IDs

Scopus: 84926364515

Host publication title

Computation Theory - 5th Symposium, Proceedings

Host publication editors

Andrzej Skowron

Access to documents

10.1007/3-540-16066-3_4

Publication metrics

Metrics

Scopus

citations

Fractional count

PlumX, opens in new tab

Captures

Citation count