Det är välkänt att modellkontroll och tillfredsställande för PLTL är PSPACE-komplett. Däremot är mycket lite känt om huruvida det finns några intressanta fragment av PLTL med en lägre värsta fall komplexitet. Sådana resultat skulle bidra till att förstå varför PLTL-modeller används med framgång i praktiken. I detta dokument undersöker vi denna fråga och överväger modellkontroll och tillfredsställande för alla fragment av PLTL som kan erhållas genom att begränsa (1) de tidsmässiga bindväv som tillåts, (2) antalet atomiska satser och (3) den tidsmässiga höjden.
Andra fragment av ltl (utan tidigare) behandlas i REF, nämligen fragment som erhålls genom att begränsa den tidsmässiga höjden och antalet atomiska förslag av formler.
The complexity of propositional linear temporal logics in simple cases
{'venue': 'Information and Computation', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}