The Power of the Depth of Iteration in Defining Relations by Induction

Amena Mahmoud

Published 2015-08-26Version 1

In this thesis we study inductive definitions over finite structures, particularly, the depth of inductive definitions. We also study infinitary finite variable logic which contains fixed-point logic and we introduce a new complexity measure $\textrm{FO}_{\bigvee}[f(n),g(n)]$ which counts the number, $f(n)$, of $\vee$-symbols, and the number, $g(n)$, of variables, in first-order formulas needed to express a given property. We prove that for $f(n)\geq \log{n}$, $\textrm{NSPACE}[f(n)] \subseteq \textrm{FO}_{\bigvee}[f(n)+\left(\frac{f(n)}{\log{n}}\right)^2,\frac{f(n)}{\log{n}}]$, and that for any $f(n),g(n)$, $\textrm{FO}_{\bigvee}[f(n),g(n)]\subseteq \textrm{DSPACE}[f(n)g(n)\log{n}]$. Also we study the expressive power of quantifier rank and number of variables and we prove that there is a property of words expressible with two variables and quantifier rank $2^n+2$ but not expressible with quantifier rank $n$ with any number of variables.