Piecewise complexity and the logic of subwords
Philippe Schnoebelen ( ENS Paris-Saclay )
- 11:00 17th May 2018 ( week 4, Trinity Term 2018 )Room 441 - Dept. of Computer Science
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:
