### Page Content

### to Navigation

## Membership problems for formulas over sets of numbers and their application to Logic

**Klaus Reinhardt (FSU Jena)**

We consider formulas (arithmetic expressions) starting with singleton sets containing a natural number of polynomial size (that means logarithmic in representation) and having some of the following operations: union, intersection, complement, addition, subtraction and upper- and lower bounds. For example if *S* is the input set from the sub-expression then {*n* ∈ N | ∀*n'* ∈ *S* → *n'* ≤ *n*} is the set produced by the upper-bounds operation.

We are interested in the complexity of the following problem: Given such a formula and a number *n* of polynomial size; Question: is *n* in the expressed set?

We show that the problem is in AC1 if we use all operations which leads to the same upper bound for model checking in a special case of modal logic. Furthermore it is in NL ∩ LogDCFL for a subset of operations which leads to the same upper bound for model checking in a special case of intuitionistic logic.

date | speaker | location | language |
---|---|---|---|

15.12.2011 17:00 | Klaus Reinhardt | FR 6510 | english/german* |

* Language is depending on the audience.