skip to main content
Idioma:
Tipo de recurso Mostra resultados com: Mostra resultados com: Índice

0–1 Laws for Fragments of Existential Second-Order Logic: A Survey

Kolaitis, Phokion G. ; Vardi, Moshe Y.

Lecture notes in computer science, 2000, p.84-98 [Periódico revisado por pares]

Berlin, Heidelberg: Springer Berlin Heidelberg

Texto completo disponível

Citações Citado por
  • Título:
    0–1 Laws for Fragments of Existential Second-Order Logic: A Survey
  • Autor: Kolaitis, Phokion G. ; Vardi, Moshe Y.
  • Assuntos: Countable Structure ; Decision Problem ; Exact sciences and technology ; Extension Axiom ; Logic and foundations ; Mathematical logic, foundations, set theory ; Mathematics ; Random Graph ; Relation Symbol ; Sciences and techniques of general use
  • É parte de: Lecture notes in computer science, 2000, p.84-98
  • Notas: Work partially supported by NSF grant CCR-9700061. Work partly done at LIFO, University of Orléans
    Work partially supported by NSF grants CCR-9610257 and CCR-9732041.
  • Descrição: The probability of a property on the collection of all finite relational structures is the limit as n → ∞ of the fraction of structures with n elements satisfying the property, provided the limit exists. It is known that the 0-1 law holds for every property expressible in first-order logic, i.e., the probability of every such property exists and is either 0 or 1. Moreover, the associated decision problem for the probabilities is solvable. In this survey, we consider fragments of existential second-order logic in which we restrict the patterns of first-order quantifiers. We focus on fragments in which the first-order part belongs to a prefix class. We show that the classifications of prefix classes of first-order logic with equality according to the solvability of the finite satisfiability problem and according to the 0-1 law for the corresponding Σ11 fragments are identical, but the classifications are different without equality.
  • Editor: Berlin, Heidelberg: Springer Berlin Heidelberg
  • Idioma: Inglês
Links
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.