Volume 7: January - December 1997

Issue 3: 1997


Expressive power and complexity in algebraic logic

  • Expressive power and complexity in algebraic logic
  • R. Hirsch

    Department of Computer Science, University College, Gower Street, London WC1E 6BT, UK. E-mail: R.Hirsch@cs.ucl.ac.uk


    Two complexity problems in algebraic logic are surveyed: the satisfaction problem and the network satisfaction problem. Various complexity results are collected here and some new ones are derived. Many examples are given. The network satisfaction problem for most cylindric algebras of dimensions four or more is shown to be intractable. Complexity is tied-in with the expressivity of a relation algebra. Expressivity and complexity are analysed in the context of homogeneous representations. The model-theoretic notion of interpretation is used to generalize known complexity results to a range of other algebraic logics. In particular a number of relation algebras are shown to have intractable network satisfaction problems.

    Keywords: Complexity, network satisfaction problem, relation algebra, cylindric algebra, interpretation

    Pages: 309 - 351

    Part of the OUP Journal of Logic and Computation WWW service

    General Information

    Click here to register with OUP.

    This page is maintained by OUP admin

    Part of the OUP Journals World Wide Web service.

    Last modification: 22 Jul 1997

    Copyright© Oxford University Press, 1997.