{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/20603"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/20603","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"The computational complexity of prefix classes of logical theories","abstract":"We derive upper and lower bounds on the computational complexity of prefix classes of several logical theories. The general method for obtaining lower bounds on the complexity of logical theories developed by Compton and Henson is adapted for their prefix classes. We are then able to show that for a fixed $r$, the prenex formulas in $\\Pi\\sb{2r+5}$ in the theory of finite trees of height at most $r$ have a $NTIME$(exp$\\sb{r-2}(c\\sqrt{n}/$log $n$)) lower bound. The same technique also gives a lower bound of $NTIME$(exp$\\sb{m}(c\\sb{m}n\\sp{1/3}/$log$\\sp2n$)) for the $\\Sigma\\sb{3m+3}$ formulas in the theory of any pairing function. We also get an upper bound for the prefix classes of the theory of $\\langle$N, $<$, +, 2$\\sp{x}\\rangle$ by analyzing the quantifier elimination procedure for this theory described by Gottsch. We show that the formulas in $\\Sigma\\sb{m}\\cup\\Pi\\sb{m}$ in this theory can be decided in $NSPACE$(exp$\\sb{m}(cmn\\sp3))$. Finally we get close upper and lower bounds for the prefix classes of the theory of finite linear orders with added unary predicates. By a direct coding of Turing machines we get that for $m\\geq2$ the formulas in $\\Pi\\sb{m}$ have an $NSPACE$(exp$\\sb{m}(d\\sb{m}n$/log $n$)) lower bound. A careful analysis of a finite automata decision procedure for this theory gives that for $m\\geq0$ the $\\Sigma\\sb{m+1}$ formulas can be decided in $NSPACE$(exp$\\sb{m}(cn\\sp2))$. We also show that the $\\Sigma\\sb1$ formulas in this theory are $NP$-complete and that the $\\Pi\\sb1$ and $\\Sigma\\sb2$ formulas are in $PSPACE$. An interpretation of this theory in the first-order theory of the binary tree with the prefix order and two successor functions shows that the formulas in $\\Sigma\\sb{m+1}$ have an $NSPACE$(exp$\\sb{m}(c\\sb{m}n/$log$\\sp2n$)) lower bound.","abstract_html":"We derive upper and lower bounds on the computational complexity of prefix classes of several logical theories. The general method for obtaining lower bounds on the complexity of logical theories developed by Compton and Henson is adapted for their prefix classes. We are then able to show that for a fixed $r$, the prenex formulas in $\\Pi\\sb{2r+5}$ in the theory of finite trees of height at most $r$ have a $NTIME$(exp$\\sb{r-2}(c\\sqrt{n}/$log $n$)) lower bound. The same technique also gives a lower bound of $NTIME$(exp$\\sb{m}(c\\sb{m}n\\sp{1/3}/$log$\\sp2n$)) for the $\\Sigma\\sb{3m+3}$ formulas in the theory of any pairing function. We also get an upper bound for the prefix classes of the theory of $\\langle$N, $&lt;$, +, 2$\\sp{x}\\rangle$ by analyzing the quantifier elimination procedure for this theory described by Gottsch. We show that the formulas in $\\Sigma\\sb{m}\\cup\\Pi\\sb{m}$ in this theory can be decided in $NSPACE$(exp$\\sb{m}(cmn\\sp3))$. Finally we get close upper and lower bounds for the prefix classes of the theory of finite linear orders with added unary predicates. By a direct coding of Turing machines we get that for $m\\geq2$ the formulas in $\\Pi\\sb{m}$ have an $NSPACE$(exp$\\sb{m}(d\\sb{m}n$/log $n$)) lower bound. A careful analysis of a finite automata decision procedure for this theory gives that for $m\\geq0$ the $\\Sigma\\sb{m+1}$ formulas can be decided in $NSPACE$(exp$\\sb{m}(cn\\sp2))$. We also show that the $\\Sigma\\sb1$ formulas in this theory are $NP$-complete and that the $\\Pi\\sb1$ and $\\Sigma\\sb2$ formulas are in $PSPACE$. An interpretation of this theory in the first-order theory of the binary tree with the prefix order and two successor functions shows that the formulas in $\\Sigma\\sb{m+1}$ have an $NSPACE$(exp$\\sb{m}(c\\sb{m}n/$log$\\sp2n$)) lower bound.","abstract_has_math":true,"creators":["Streid, David Benjamin"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Schupp, Paul E."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T12:43:59Z","date_published":"2011-05-07T12:43:59Z","updated_at":"2026-07-22T22:25:16Z","subjects":["Mathematics","Computer Science"],"languages":["eng"],"rights":["Copyright 1990 Streid, David Benjamin"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9021763","(UMI)AAI9021763"],"render_values":[{"text":"AAI9021763","href":null,"code":true},{"text":"(UMI)AAI9021763","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/20603","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Schupp, Paul E."]},{"key":"dc:creator","label":"Author","values":["Streid, David Benjamin"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T12:43:59Z","10000-01-01","1990"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics","Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1990 Streid, David Benjamin"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9021763","(UMI)AAI9021763","http://hdl.handle.net/2142/20603"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["We derive upper and lower bounds on the computational complexity of prefix classes of several logical theories. The general method for obtaining lower bounds on the complexity of logical theories developed by Compton and Henson is adapted for their prefix classes. We are then able to show that for a fixed $r$, the prenex formulas in $\\Pi\\sb{2r+5}$ in the theory of finite trees of height at most $r$ have a $NTIME$(exp$\\sb{r-2}(c\\sqrt{n}/$log $n$)) lower bound. The same technique also gives a lower bound of $NTIME$(exp$\\sb{m}(c\\sb{m}n\\sp{1/3}/$log$\\sp2n$)) for the $\\Sigma\\sb{3m+3}$ formulas in the theory of any pairing function. We also get an upper bound for the prefix classes of the theory of $\\langle$N, $<$, +, 2$\\sp{x}\\rangle$ by analyzing the quantifier elimination procedure for this theory described by Gottsch. We show that the formulas in $\\Sigma\\sb{m}\\cup\\Pi\\sb{m}$ in this theory can be decided in $NSPACE$(exp$\\sb{m}(cmn\\sp3))$. Finally we get close upper and lower bounds for the prefix classes of the theory of finite linear orders with added unary predicates. By a direct coding of Turing machines we get that for $m\\geq2$ the formulas in $\\Pi\\sb{m}$ have an $NSPACE$(exp$\\sb{m}(d\\sb{m}n$/log $n$)) lower bound. A careful analysis of a finite automata decision procedure for this theory gives that for $m\\geq0$ the $\\Sigma\\sb{m+1}$ formulas can be decided in $NSPACE$(exp$\\sb{m}(cn\\sp2))$. We also show that the $\\Sigma\\sb1$ formulas in this theory are $NP$-complete and that the $\\Pi\\sb1$ and $\\Sigma\\sb2$ formulas are in $PSPACE$. An interpretation of this theory in the first-order theory of the binary tree with the prefix order and two successor functions shows that the formulas in $\\Sigma\\sb{m+1}$ have an $NSPACE$(exp$\\sb{m}(c\\sb{m}n/$log$\\sp2n$)) lower bound.","Made available in DSpace on 2011-05-07T12:43:59Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9021763.pdf: 3928648 bytes, checksum: d5f91807b61b8520eaf0f7ece43d97fb (MD5) Previous issue date: 1990","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:45:00Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:19:53-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["The computational complexity of prefix classes of logical theories"]}]}],"canonical_facts":{"dc:contributor":["Schupp, Paul E."],"dc:creator":["Streid, David Benjamin"],"dc:date":["2011-05-07T12:43:59Z","10000-01-01","1990"],"dc:description":["We derive upper and lower bounds on the computational complexity of prefix classes of several logical theories. The general method for obtaining lower bounds on the complexity of logical theories developed by Compton and Henson is adapted for their prefix classes. We are then able to show that for a fixed $r$, the prenex formulas in $\\Pi\\sb{2r+5}$ in the theory of finite trees of height at most $r$ have a $NTIME$(exp$\\sb{r-2}(c\\sqrt{n}/$log $n$)) lower bound. The same technique also gives a lower bound of $NTIME$(exp$\\sb{m}(c\\sb{m}n\\sp{1/3}/$log$\\sp2n$)) for the $\\Sigma\\sb{3m+3}$ formulas in the theory of any pairing function. We also get an upper bound for the prefix classes of the theory of $\\langle$N, $<$, +, 2$\\sp{x}\\rangle$ by analyzing the quantifier elimination procedure for this theory described by Gottsch. We show that the formulas in $\\Sigma\\sb{m}\\cup\\Pi\\sb{m}$ in this theory can be decided in $NSPACE$(exp$\\sb{m}(cmn\\sp3))$. Finally we get close upper and lower bounds for the prefix classes of the theory of finite linear orders with added unary predicates. By a direct coding of Turing machines we get that for $m\\geq2$ the formulas in $\\Pi\\sb{m}$ have an $NSPACE$(exp$\\sb{m}(d\\sb{m}n$/log $n$)) lower bound. A careful analysis of a finite automata decision procedure for this theory gives that for $m\\geq0$ the $\\Sigma\\sb{m+1}$ formulas can be decided in $NSPACE$(exp$\\sb{m}(cn\\sp2))$. We also show that the $\\Sigma\\sb1$ formulas in this theory are $NP$-complete and that the $\\Pi\\sb1$ and $\\Sigma\\sb2$ formulas are in $PSPACE$. An interpretation of this theory in the first-order theory of the binary tree with the prefix order and two successor functions shows that the formulas in $\\Sigma\\sb{m+1}$ have an $NSPACE$(exp$\\sb{m}(c\\sb{m}n/$log$\\sp2n$)) lower bound.","Made available in DSpace on 2011-05-07T12:43:59Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9021763.pdf: 3928648 bytes, checksum: d5f91807b61b8520eaf0f7ece43d97fb (MD5) Previous issue date: 1990","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:45:00Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:19:53-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9021763","(UMI)AAI9021763","http://hdl.handle.net/2142/20603"],"dc:language":["eng"],"dc:rights":["Copyright 1990 Streid, David Benjamin"],"dc:subject":["Mathematics","Computer Science"],"dc:title":["The computational complexity of prefix classes of logical theories"],"dc:type":["text"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:16Z"}