𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Linear Time and the Power of One First-Order Universal Quantifier

✍ Scribed by Arnaud Durand

Book ID
118768972
Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
120 KB
Volume
178
Category
Article
ISSN
0890-5401

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

The first-order theory of linear one-ste
The first-order theory of linear one-step rewriting is undecidable
✍ Ralf Treinen πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 758 KB

The theory of one-step rewriting for a given rewrite system R and signature C is the firstorder theory of the following structure: its universe consists of all C-ground terms, and its only predicate is the relation "x rewrites to y in one step by R". The structure contains no function symbols and no

The quantifier complexity of polynomial-
The quantifier complexity of polynomial-size iterated definitions in first-order logic
✍ Samuel R. Buss; Alan S. Johnson πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 208 KB

## Abstract We refine the constructions of Ferrante‐Rackoff and Solovay on iterated definitions in first‐order logic and their expressibility with polynomial size formulas. These constructions introduce additional quantifiers; however, we show that these extra quantifiers range over only finite set