6533b873fe1ef96bd12d4c07

RESEARCH PRODUCT

Padding and the expressive power of existential second-order logics

Thomas Schwentick

subject

Discrete mathematicsComputational complexity theoryComputer sciencePaddingExpressive powerExistentialismGraphVertex (geometry)CombinatoricsLogical programmingComplexity classIsomorphismUnary functionMathematicsofComputing_DISCRETEMATHEMATICS

description

Padding techniques are well-known from Computational Complexity Theory. Here, an analogous concept is considered in the context of existential second-order logics. Informally, a graph H is a padded version of a graph G, if H consists of an isomorphic copy of G and some isolated vertices. A set A of graphs is called weakly expressible by a formula ϕ in the presence of padding, if ϕ is able to distinguish between (sufficiently) padded versions of graphs from A and padded versions of graphs that are not in A.

https://doi.org/10.1007/bfb0028031