SIMPL · Specification and Implementation of Pattern Languages

The proposal is aimed at helping to provide robust and transparent data infrastructure for the future Internet (which is a part of the European Commission ICT Challenge 1: Pervasive and Trustworthy Network and Service Infrastructures). The primary object of research is data, in contrast with computation. Therefore we will be interested mainly in kinds of formal data certification rather than in certified interpreters, etc. This however does not exclude possibilities for a crossroad research where these two paradigms overlap. Research objectives: 1) Theoretical representation of extended, or, practical, regular expressions in constructive dependent type theory. (We will overcome redundant assumptions regarding equality of languages that lay in the foundation of today's simply typed theories of practical regular expressions.) 2) A Coq library for regular languages and automata that includes features not present in available related libraries, such as extended regular expressions and partial derivatives of regular expressions; and a Coq library for pattern languages that provides full support for backreferences. 3) A formally certified compiler of patterns into automata; a formally certified grep-like pattern parser. 4) A formally certified UTF-8 encoder/decoder. 5) A formally certified data description language for describing binary data format specifications with a possibility to prove meta-properties of data specifications, such as completeness or consistency; in other words, a language for production of formally certified specifications of data formats. Main research questions: 1) What is the efficiency of the derivative approach in computation of context-sensitive features or extended regular expressions? 2) How can one define partial derivatives of regular expressions with backreferences? 3) What is the dependent type of partial derivatives of regular expressions with backreferences?