direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

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'Sn'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.

Back to the research colloquium site.

Zusatzinformationen / Extras