Skip to main content

Piecewise complexity and the logic of subwords

Philippe Schnoebelen ( ENS Paris-Saclay )

Piecewise complexity is a new descriptive complexity measure for words and languages, based on the length of subwords used in their piecewise definitions.
Piecewise complexity was introduced in connection with logic-related decision problems. In particular, it allowed deriving elementary complexity uppoer bounds for the two-variable fragments of the logic of subwords.

Share this: