6533b873fe1ef96bd12d4c07
RESEARCH PRODUCT
Padding and the expressive power of existential second-order logics
Thomas Schwenticksubject
Discrete mathematicsComputational complexity theoryComputer sciencePaddingExpressive powerExistentialismGraphVertex (geometry)CombinatoricsLogical programmingComplexity classIsomorphismUnary functionMathematicsofComputing_DISCRETEMATHEMATICSdescription
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.
year | journal | country | edition | language |
---|---|---|---|---|
1998-01-01 |