Auflistung nach Schlagwort "Logspace"

Sortiert nach: Sortierung: Ergebnisse:

  • Parameterised Counting in Logspace 
    Haak, Anselm; Meier, Arne; Prakash, Om; Rao, B. V. Raghavendra (New York, NY : Springer, 2023)
    Logarithmic space-bounded complexity classes such as L and NL play a central role in space-bounded computation. The study of counting versions of these complexity classes have lead to several interesting insights into the ...
  • The Tractability of Model-checking for LTL: The Good, the Bad, and the Ugly Fragments 
    Bauland, Michael; Mundhenk, Martin; Schneider, Thomas; Schnoor, Henning; Schnoor, Ilka; Vollmer, Heribert (Amsterdam : Elsevier, 2009)
    In a seminal paper from 1985, Sistla and Clarke showed that the model-checking problem for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete, depending on the set of temporal operators used. If, in ...