Derivatives for Enhanced Regular Expressions

详细信息    查看全文

• 关键词：Automata and logic ; Regular languages ; Derivatives
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9705
• 期：1
• 页码：285-297
• 全文大小：278 KB
• 参考文献：1.Antimirov, V.M.: Rewriting regular inequalities. In: Reichel, H. (ed.) FCT 1995. LNCS, vol. 965, pp. 116–125. Springer, Heidelberg (1995)CrossRef
  2.Antimirov, V.M.: Partial derivatives of regular expressions and finite automaton constructions. Theor. Comput. Sci. 155(2), 291–319 (1996)MathSciNet CrossRef MATH
  3.Broda, S., Machiavelo, A., Moreira, N., Reis, R.: Study of the average size of Glushkov and partial derivative automata, October 2011
  4.Brzozowski, J.A.: Derivatives of regular expressions. J. ACM 11(4), 481–494 (1964)MathSciNet CrossRef MATH
  5.Caron, P., Champarnaud, J.-M., Mignot, L.: Partial derivatives of an extended regular expression. In: Dediu, A.-H., Inenaga, S., Martín-Vide, C. (eds.) LATA 2011. LNCS, vol. 6638, pp. 179–191. Springer, Heidelberg (2011)CrossRef
  6.Caron, P., Champarnaud, J.-M., Mignot, L.: Multi-tilde-bar derivatives. In: Moreira, N., Reis, R. (eds.) CIAA 2012. LNCS, vol. 7381, pp. 321–328. Springer, Heidelberg (2012)CrossRef
  7.Caron, P., Champarnaud, J., Mignot, L.: A general framework for the derivation of regular expressions. RAIRO Theor. Inf. Appl. 48(3), 281–305 (2014)MathSciNet CrossRef MATH
  8.Champarnaud, J.-M., Jeanne, H., Mignot, L.: Approximate regular expressions and their derivatives. In: Dediu, A.-H., Martín-Vide, C. (eds.) LATA 2012. LNCS, vol. 7183, pp. 179–191. Springer, Heidelberg (2012)CrossRef
  9.Grabmayer, C.: Using proofs by coinduction to find “Traditional” proofs. In: Fiadeiro, J.L., Harman, N.A., Roggenbach, M., Rutten, J. (eds.) CALCO 2005. LNCS, vol. 3629, pp. 175–193. Springer, Heidelberg (2005)CrossRef
  10.Might, M., Darais, D., Spiewak, D.: Parsing with derivatives: a functional pearl. In: Proceedings of ICFP 2011, pp. 189–195. ACM (2011)
  11.Owens, S., Reppy, J., Turon, A.: Regular-expression derivatives reexamined. J. Funct. Program. 19(2), 173–190 (2009)MathSciNet CrossRef MATH
  12.Roşu, G., Viswanathan, M.: Testing extended regular language membership incrementally by rewriting. In: Nieuwenhuis, R. (ed.) RTA 2003. LNCS, vol. 2706, pp. 499–514. Springer, Heidelberg (2003)CrossRef
  13.Sulzmann, M., Thiemann, P.: Derivatives for regular shuffle expressions. In: Dediu, A.-H., Formenti, E., Martín-Vide, C., Truthe, B. (eds.) LATA 2015. LNCS, vol. 8977, pp. 275–286. Springer, Heidelberg (2015)
  14.Sulzmann, M., Thiemann, P.: Forkable regular expressions. In: Dediu, A.-H., Janoušek, J., Martín-Vide, C., Truthe, B. (eds.) LATA 2016. LNCS, vol. 9618, pp. 194–206. Springer, Heidelberg (2016). doi:10.​1007/​978-3-319-30000-9_​15 CrossRef
  15.Traytel, D., Nipkow, T.: Verified decision procedures for MSO on words based on derivatives of regular expressions. J. Funct. Program. 25, e18 (2015)MathSciNet CrossRef MATH
  16.Watson, B.W.: FIRE lite: FAs and REs in C++. In: Raymond, D.R., Yu, S., Wood, D. (eds.) WIA 1996. LNCS, vol. 1260, pp. 167–188. Springer, Heidelberg (1997)CrossRef
  
• 作者单位：Peter Thiemann (15)
  
  15. University of Freiburg, Freiburg im Breisgau, Germany
  
• 丛书名：Implementation and Application of Automata
• ISBN：978-3-319-40946-7
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9705

文摘

Regular languages are closed under a wealth of formal language operators. Incorporating such operators in regular expressions leads to concise language specifications, but the transformation of such enhanced regular expressions to finite automata becomes more involved. We present an approach that enables the direct construction of finite automata from regular expressions enhanced with further operators that preserve regularity. Our construction is based on an extension of the theory of derivatives for regular expressions. To retain the standard results about derivatives, we develop a derivability criterion for the compatibility of the extra operators with derivatives.