6533b837fe1ef96bd12a30c7

RESEARCH PRODUCT

On bijections vs. unary functions

Thomas Schwentick

subject

CombinatoricsSet (abstract data type)Range (mathematics)Unary operationHierarchy (mathematics)Computer Science::Logic in Computer ScienceOrder (group theory)Unary functionArityBijection injection and surjectionComputer Science::Formal Languages and Automata TheoryMathematics

description

A set of finite structures is in Binary NP if it can be characterized by existential second order formulas in which second order quantification is over relations of arity 2. In [DLS95] subclasses of Binary NP were considered, in which the second order quantifiers range only over certain classes of relations. It was shown that many of these subclasses coincide and that all of them can be ordered in a three-level linear hierarchy, the levels of which are represented by bijections, successor relations and unary functions respectively.

yearjournalcountryeditionlanguage
1996-01-01
https://doi.org/10.1007/3-540-60922-9_34