Paper: A small universal model for system executions (at LICS 1989)

Authors: Jay L. Gischer

Abstract

The author shows that every consistent set of atomic relations has a unified model of size roughly O(n²). This model can be used to give a simplified proof of completeness of some axioms. He gives several complexity results for deciding the theory of several classes of axiom sets, for both partial models and global-time models, showing many such variations to have the same complexity as transitive closure or matrix multiplication. The author shows that deciding disjunctive axioms is NP-complete for both the global-time and the standard model

BibTeX

  @InProceedings{Gischer-Asmalluniversalmode,
    author = 	 {Jay L. Gischer},
    title = 	 {A small universal model for system executions},
    booktitle =  {Proceedings of the Fourth Annual IEEE Symposium on Logic in Computer Science (LICS 1989)},
    year =	 {1989},
    month =	 {June}, 
    pages =      {146--153},
    location =   {Pacific Grove, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }