Till sidans topp

Sidansvarig: Webbredaktion
Sidan uppdaterades: 2012-09-11 15:12

Tipsa en vän
Utskriftsversion

A Decision Procedure for … - Göteborgs universitet Till startsida
Webbkarta
Till innehåll Läs mer om hur kakor används på gu.se

A Decision Procedure for Regular Expression Equivalence in Type Theory

Paper i proceeding
Författare Thierry Coquand
Vincent Siles
Publicerad i Certified Programs and Proofs : First International Conference, CPP 2011, Kenting, Taiwan, December 7-9, 2011. Proceedings / edited by Jean-Pierre Jouannaud, Zhong Shao
Volym 7086
Sidor 119-134
ISBN 978-3-642-25379-9
ISSN 0302-9743
Publiceringsår 2011
Publicerad vid Institutionen för data- och informationsteknik (GU)
Sidor 119-134
Språk en
Länkar dx.doi.org/10.1007/978-3-642-25379-...
Ämneskategorier

Sammanfattning

We describe and formally verify a procedure to decide regular expressions equivalence: two regular expressions are equivalent if and only if they recognize the same language. Our approach to this problem is inspired by Brzozowski’s algorithm using derivatives of regular expressions, with a new definition of finite sets. In this paper, we detail a complete formalization of Brzozowki’s derivatives, a new definition of finite sets along with its basic meta-theory, and a decidable equivalence procedure correctly proved using Coq and Ssreflect.

Sidansvarig: Webbredaktion|Sidan uppdaterades: 2012-09-11
Dela:

På Göteborgs universitet använder vi kakor (cookies) för att webbplatsen ska fungera på ett bra sätt för dig. Genom att surfa vidare godkänner du att vi använder kakor.  Vad är kakor?