IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

The computational complexity of prefix classes of logical theories

Show full item record

Bookmark or cite this item: http://hdl.handle.net/2142/20603

Files in this item

File Description Format
PDF 9021763.pdf (4MB) Restricted to U of Illinois (no description provided) PDF
Title: The computational complexity of prefix classes of logical theories
Author(s): Streid, David Benjamin
Doctoral Committee Chair(s): Schupp, Paul E.
Department / Program: Mathematics
Discipline: Mathematics
Degree Granting Institution: University of Illinois at Urbana-Champaign
Degree: Ph.D.
Genre: Dissertation
Subject(s): Mathematics Computer Science
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.
Issue Date: 1990
Type: Text
Language: English
URI: http://hdl.handle.net/2142/20603
Rights Information: Copyright 1990 Streid, David Benjamin
Date Available in IDEALS: 2011-05-07
Identifier in Online Catalog: AAI9021763
OCLC Identifier: (UMI)AAI9021763
 

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 0
  • Downloads this Month: 0
  • Downloads Today: 0

Browse

My Account

Information

Access Key