294:
Pratt-Hartmann, Ian; Szwast, Wieslaw; Tendera, Lidia (2016), "Quine's fluted fragment is non-elementary", in Talbot, Jean-Marc; Regnier, Laurent (eds.),
253:
Automated
Deduction — CADE-13: 13th International Conference on Automated Deduction New Brunswick, NJ, USA, July 30 – August 3, 1996, Proceedings
504:
389:
528:
36:
323:
440:
278:
156:
497:
296:
25th EACSL Annual
Conference on Computer Science Logic, CSL 2016, August 29 - September 1, 2016, Marseille, France
17:
131:
Proceedings of the
Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS '98)
490:
470:
523:
46:
261:
139:
298:, LIPIcs, vol. 62, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 39:1–39:21,
478:
256:
134:
86:
77:
237:
96:
82:
184:
8:
251:
Vorobyov, Sergei (1996), "An improved lower bound for the elementary theories of trees",
50:
418:
365:
215:
162:
104:
90:
436:
336:
274:
152:
71:
54:
166:
428:
340:
332:
299:
266:
225:
180:
144:
42:
229:
432:
394:
318:
255:, Lecture Notes in Computer Science, vol. 1104, Springer, pp. 275–287,
233:
126:
474:
410:
304:
67:
517:
364:. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS).
270:
203:
31:
Examples of nonelementary problems that are nevertheless decidable include:
61:
148:
415:
2021 IEEE 62nd Annual
Symposium on Foundations of Computer Science (FOCS)
345:
129:(1998), "Complexity of Nonrecursive Logic Programs with Complex Values",
25:
220:
100:
411:"The Reachability Problem for Petri Nets is Not Primitive Recursive"
423:
370:
390:"An Easy-Sounding Problem Yields Numbers Too Big for Our Universe"
186:
The
Complexity of Decision Problems in Automata Theory and Logic
362:
Reachability in Vector
Addition Systems is Ackermann-complete
321:(1979), "The typed λ-calculus is not elementary recursive",
293:
192:, Ph.D. dissertation, Massachusetts Institute of Technology
28:. As a class it is sometimes denoted as NONELEMENTARY.
359:
37:
regular expression equivalence with complementation
206:(2006), "Logics for unranked trees: an overview",
360:Czerwiński, Wojciech; Orlikowski, Łukasz (2021).
76:deciding β-convertibility of two closed terms in
515:
124:
24:is a problem that is not a member of the class
498:
133:, New York, NY, USA: ACM, pp. 244–253,
505:
491:
179:
422:
369:
344:
303:
260:
219:
138:
387:
250:
317:
516:
408:
202:
456:
383:
381:
208:Logical Methods in Computer Science
13:
529:Theoretical computer science stubs
14:
540:
388:Brubaker, Ben (4 December 2023).
378:
409:Leroux, Jerome (February 2022).
18:computational complexity theory
402:
353:
311:
287:
244:
196:
173:
118:
1:
111:
477:. You can help Knowledge by
471:theoretical computer science
433:10.1109/FOCS52979.2021.00121
417:. IEEE. pp. 1241–1252.
337:10.1016/0304-3975(79)90007-0
324:Theoretical Computer Science
7:
10:
545:
455:
305:10.4230/LIPIcs.CSL.2016.39
47:monadic second-order logic
60:the decision problem for
271:10.1007/3-540-61511-3_91
230:10.2168/LMCS-2(3:2)2006
87:vector addition systems
473:–related article is a
70:'s fluted fragment of
149:10.1145/275487.275515
78:typed lambda calculus
22:nonelementary problem
181:Stockmeyer, Larry J.
524:Complexity classes
125:Vorobyov, Sergei;
66:satisfiability of
486:
485:
442:978-1-6654-2055-6
280:978-3-540-61511-8
158:978-0-89791-996-8
72:first-order logic
536:
507:
500:
493:
462:P ≟ NP
457:
447:
446:
426:
406:
400:
399:
385:
376:
375:
373:
357:
351:
349:
348:
319:Statman, Richard
315:
309:
308:
307:
291:
285:
283:
264:
248:
242:
240:
223:
200:
194:
193:
191:
177:
171:
169:
142:
127:Voronkov, Andrei
122:
43:decision problem
544:
543:
539:
538:
537:
535:
534:
533:
514:
513:
512:
511:
464:
453:
451:
450:
443:
407:
403:
395:Quanta Magazine
386:
379:
358:
354:
316:
312:
292:
288:
281:
249:
245:
201:
197:
189:
178:
174:
159:
123:
119:
114:
35:the problem of
12:
11:
5:
542:
532:
531:
526:
510:
509:
502:
495:
487:
484:
483:
466:
460:
449:
448:
441:
401:
377:
352:
310:
286:
279:
262:10.1.1.39.1499
243:
214:(3): 3:2, 31,
204:Libkin, Leonid
195:
172:
157:
140:10.1.1.39.8822
116:
115:
113:
110:
109:
108:
94:
80:
74:
68:W. V. O. Quine
64:
58:
39:
9:
6:
4:
3:
2:
541:
530:
527:
525:
522:
521:
519:
508:
503:
501:
496:
494:
489:
488:
482:
480:
476:
472:
467:
463:
459:
458:
454:
444:
438:
434:
430:
425:
420:
416:
412:
405:
397:
396:
391:
384:
382:
372:
367:
363:
356:
347:
346:2027.42/23535
342:
338:
334:
330:
326:
325:
320:
314:
306:
301:
297:
290:
282:
276:
272:
268:
263:
258:
254:
247:
239:
235:
231:
227:
222:
221:cs.LO/0606062
217:
213:
209:
205:
199:
188:
187:
182:
176:
168:
164:
160:
154:
150:
146:
141:
136:
132:
128:
121:
117:
106:
102:
98:
95:
92:
88:
84:
81:
79:
75:
73:
69:
65:
63:
62:term algebras
59:
56:
52:
48:
44:
40:
38:
34:
33:
32:
29:
27:
23:
19:
479:expanding it
468:
461:
452:
414:
404:
393:
361:
355:
328:
322:
313:
295:
289:
252:
246:
211:
207:
198:
185:
175:
130:
120:
97:reachability
83:reachability
30:
21:
15:
518:Categories
424:2104.12695
371:2104.13866
112:References
107:-complete.
101:Petri nets
93:-complete.
26:ELEMENTARY
331:: 73–81,
257:CiteSeerX
135:CiteSeerX
105:Ackermann
91:Ackermann
183:(1974),
167:15631793
103:; it is
89:; it is
238:2295773
465:
439:
277:
259:
236:
165:
155:
137:
469:This
419:arXiv
366:arXiv
216:arXiv
190:(PDF)
163:S2CID
53:(see
51:trees
49:over
20:, a
475:stub
437:ISBN
275:ISBN
153:ISBN
45:for
41:the
429:doi
341:hdl
333:doi
300:doi
267:doi
226:doi
145:doi
99:in
85:in
55:S2S
16:In
520::
435:.
427:.
413:.
392:.
380:^
339:,
327:,
273:,
265:,
234:MR
232:,
224:,
210:,
161:,
151:,
143:,
506:e
499:t
492:v
481:.
445:.
431::
421::
398:.
374:.
368::
350:.
343::
335::
329:9
302::
284:.
269::
241:.
228::
218::
212:2
170:.
147::
57:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.