On bounded theories
Arising in the context of the relationship between the computational complexity of a query and its expressibility in first-order logic with a fixed number of bound variables, \textit{N. Immerman} and \textit{D. Kozen} [Inf. Comput. 83, 121-139 (1989; Zbl 0711.03004)] have studied theories satisfying the ``\(k\)-variable property (every first-order formula is equivalent under theory \(\Sigma\) to a formula with at most \(k\) bound variables). Since the notion of \(k\)-variable property of Immerman and Kozen [loc. cit.] proved to be not ``stable, the author introduces the (more restrictive) notion of \(k\)-boundedness: a theory \(\Sigma\) is \(k\)- bounded if every first-order formula \(\varphi(x_ 1,\dots,x_ n)\), with \(n\geq k\), is equivalent to a formula \(\psi(x_ 1,\dots,x_ n)\) with bound variables among \(x_ 1,\dots,x_ n\) such that in each subformula at most \(k\) variables are in the scope of a quantifier of \(\varphi\). The new definition entails interesting results: (1) Every \(k\)-bounded theory is \((k+1)\)-bounded; (2) Every \(k\)-bounded theory has the \(k\)-variable property; (3) The examples of theories of Immerman and Kozen [loc. cit.] having the \(k\)-variable property are \(k\)-bounded; (4) There is an algebraic characterization of \(k\)-boundedness in terms of partial isomorphisms; (5) The use of \(\omega\)-saturated structures simplifies considerably the proofs. For the entire collection see [Zbl 0772.68004].
- Definability with bounded number of bound variables
- Complexity Results for First-Order Two-Variable Logic with Counting
- scientific article; zbMATH DE number 1302669
- Finite Variable Logics in Descriptive Complexity Theory
- How many first-order variables are needed on finite ordered structures?
- Bounded-variable fixpoint queries are PSPACE-complete
- Complexity of finite-variable fragments of EXPTIME-complete logics
- Types and indiscernibles in finite models
- The undecidability of k-provability
- Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics
- There is no recursive link between the k-size of a model and its cardinality
- First-order concatenation theory with bounded quantifiers
- Bounded theories for polyspace computability
- Large finite structures with few \(L^k\)-types
- Number of variables is equivalent to space
- scientific article; zbMATH DE number 1163985 (Why is no real title available?)
- On L^k (Q) types and boundedness of IFP (Q) on finite structures
- The \(k\)-variable property is stronger than H-dimension \(k\)
- Uniformly bounded arrays and mutually algebraic structures
- Bounded and well-placed theories in the lattice of equational theories
This page was built for publication: On bounded theories
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4202936)