160:
36:
of the fragment are a subset of those in the original logic. However, the semantics of the formulae in the fragment and in the logic coincide, and any formula of the fragment can be expressed in the original logic.
201:
64:
that are as expressive as possible yet are decidable or more strongly have low computational complexity. The field of
138:
111:
69:
41:
65:
220:
25:
194:
52:
for the logical fragment can be no higher than the same tasks in the original logic, as there is a
53:
128:
101:
225:
175:
8:
187:
127:
Ebbinghaus, Heinz-Dieter; Flum, Jörg (2005), "Chapter 7. Descriptive
Complexity Theory",
57:
33:
17:
134:
107:
61:
73:
103:
The
Calculus of Computation: Decision Procedures with Applications to Verification
171:
49:
45:
214:
97:
133:, Perspectives in mathematical logic, Springer, pp. 119–164,
72:, by identifying logical fragments that exactly capture certain
159:
29:
167:
56:
from the first problem to the other. An important problem in
28:
is a subset of this logical language obtained by imposing
60:
is to determine fragments of well-known logics such as
212:
68:aims at establishing a link between logics and
126:
195:
95:
202:
188:
32:restrictions on the language. Hence, the
213:
154:
91:
89:
13:
14:
237:
86:
158:
70:computational complexity theory
120:
1:
79:
66:descriptive complexity theory
174:. You can help Knowledge by
7:
10:
242:
153:
24:of a logical language or
106:, Springer, p. 70,
42:computational complexity
170:-related article is a
34:well-formed formulae
130:Finite Model Theory
96:Bradley, Aaron R.;
58:computational logic
221:Mathematical logic
74:complexity classes
18:mathematical logic
183:
182:
62:first-order logic
44:of tasks such as
233:
204:
197:
190:
162:
155:
145:
143:
124:
118:
116:
93:
241:
240:
236:
235:
234:
232:
231:
230:
211:
210:
209:
208:
151:
149:
148:
141:
125:
121:
114:
94:
87:
82:
12:
11:
5:
239:
229:
228:
223:
207:
206:
199:
192:
184:
181:
180:
163:
147:
146:
139:
119:
112:
84:
83:
81:
78:
50:model checking
46:satisfiability
9:
6:
4:
3:
2:
238:
227:
224:
222:
219:
218:
216:
205:
200:
198:
193:
191:
186:
185:
179:
177:
173:
169:
164:
161:
157:
156:
152:
142:
140:9783540287889
136:
132:
131:
123:
115:
113:9783540741138
109:
105:
104:
99:
92:
90:
85:
77:
75:
71:
67:
63:
59:
55:
51:
47:
43:
38:
35:
31:
27:
23:
19:
176:expanding it
165:
150:
129:
122:
102:
98:Manna, Zohar
39:
21:
15:
226:Logic stubs
30:syntactical
215:Categories
80:References
54:reduction
100:(2007),
22:fragment
137:
110:
26:theory
168:logic
166:This
172:stub
135:ISBN
108:ISBN
40:The
20:, a
48:or
16:In
217::
88:^
76:.
203:e
196:t
189:v
178:.
144:.
117:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
