{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T00:48:32Z","timestamp":1772498912686,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642333132","type":"print"},{"value":"9783642333149","type":"electronic"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33314-9_7","type":"book-chapter","created":{"date-parts":[[2012,9,12]],"date-time":"2012-09-12T04:05:18Z","timestamp":1347422718000},"page":"98-113","source":"Crossref","is-referenced-by-count":11,"title":["Deciding Regular Expressions (In-)Equivalence in Coq"],"prefix":"10.1007","author":[{"given":"Nelma","family":"Moreira","sequence":"first","affiliation":[]},{"given":"David","family":"Pereira","sequence":"additional","affiliation":[]},{"given":"Sim\u00e3o","family":"Melo de Sousa","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"7_CR1","unstructured":"Filli\u00e2tre, J.C.: Finite Automata Theory in Coq: A constructive proof of Kleene\u2019s theorem. Research Report 97\u201304, LIP - ENS Lyon (February 1997)"},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"Kleene, S.: In: Shannon, C., McCarthy, J. (eds.) Representation of Events in Nerve Nets and Finite Automata, pp. 3\u201342. Princeton University Press","DOI":"10.1515\/9781400882618-002"},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"Bertot, Y., Cast\u00e9ran, P.: Interactive Theorem Proving and Program Development. Coq\u2019Art: The Calculus of Inductive Constructions. Texts in Theoretical Computer Science. Springer (2004)","DOI":"10.1007\/978-3-662-07964-5"},{"key":"7_CR4","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/978-3-540-73595-3_19","volume-title":"Automated Deduction \u2013 CADE-21","author":"P. H\u00f6fner","year":"2007","unstructured":"H\u00f6fner, P., Struth, G.: Automated Reasoning in Kleene Algebra. In: Pfenning, F. (ed.) CADE 2007. LNCS (LNAI), vol.\u00a04603, pp. 279\u2013294. Springer, Heidelberg (2007)"},{"key":"7_CR5","unstructured":"McCune, W.: Prover9 and Mace4, http:\/\/www.cs.unm.edu\/smccune\/mace4 (access date: October 1, 2011)"},{"key":"7_CR6","unstructured":"Moreira, N., Pereira, D.: KAT and PHL in Coq. CSIS\u00a005 (02) (December 2008) ISSN: 1820-0214"},{"issue":"3","key":"7_CR7","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1145\/256167.256195","volume":"19","author":"D. Kozen","year":"1997","unstructured":"Kozen, D.: Kleene algebra with tests. Transactions on Programming Languages and Systems\u00a019(3), 427\u2013443 (1997)","journal-title":"Transactions on Programming Languages and Systems"},{"key":"7_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/978-3-642-18098-9_7","volume-title":"Implementation and Application of Automata","author":"J.B. Almeida","year":"2011","unstructured":"Almeida, J.B., Moreira, N., Pereira, D., Melo de Sousa, S.: Partial Derivative Automata Formalized in Coq. In: Domaratzki, M., Salomaa, K. (eds.) CIAA 2010. LNCS, vol.\u00a06482, pp. 59\u201368. Springer, Heidelberg (2011)"},{"issue":"4","key":"7_CR9","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1142\/S0129054109006802","volume":"20","author":"M. Almeida","year":"2009","unstructured":"Almeida, M., Moreira, N., Reis, R.: Antimirov and Mosses\u2019s rewrite system revisited. Int. J. Found. Comput. Sci.\u00a020(4), 669\u2013684 (2009)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"7_CR10","unstructured":"Antimirov, V.M., Mosses, P.D.: Rewriting extended regular expressions. In: Rozenberg, G., Salomaa, A. (eds.) DLT, pp. 195\u2013209. World Scientific (1994)"},{"key":"7_CR11","unstructured":"Hopcroft, J., Karp, R.M.: A linear algorithm for testing equivalence of finite automata. Technical Report TR 71-114, University of California, Berkeley, California (1971)"},{"issue":"1\/2","key":"7_CR12","first-page":"7","volume":"15","author":"M. Almeida","year":"2010","unstructured":"Almeida, M., Moreira, N., Reis, R.: Testing regular languages equivalence. JALC\u00a015(1\/2), 7\u201325 (2010)","journal-title":"JALC"},{"key":"7_CR13","unstructured":"Almeida, M.: Equivalence of regular languages: an algorithmic approach and complexity analysis. PhD thesis, FCUP (2011), http:\/\/www.dcc.fc.up.pt\/~mfa\/thesis.pdf"},{"key":"7_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-642-22321-1_9","volume-title":"Developments in Language Theory","author":"S. Broda","year":"2011","unstructured":"Broda, S., Machiavelo, A., Moreira, N., Reis, R.: The Average Transition Complexity of Glushkov and Partial Derivative Automata. In: Mauri, G., Leporati, A. (eds.) DLT 2011. LNCS, vol.\u00a06795, pp. 93\u2013104. Springer, Heidelberg (2011)"},{"key":"7_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/978-3-642-14052-5_13","volume-title":"Interactive Theorem Proving","author":"T. Braibant","year":"2010","unstructured":"Braibant, T., Pous, D.: An Efficient Coq Tactic for Deciding Kleene Algebras. In: Kaufmann, M., Paulson, L.C. (eds.) ITP 2010. LNCS, vol.\u00a06172, pp. 163\u2013178. Springer, Heidelberg (2010)"},{"issue":"2","key":"7_CR16","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1006\/inco.1994.1037","volume":"110","author":"D. Kozen","year":"1994","unstructured":"Kozen, D.: A completeness theorem for Kleene algebras and the algebra of regular events. Infor. and Comput.\u00a0110(2), 366\u2013390 (1994)","journal-title":"Infor. and Comput."},{"key":"7_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/978-3-642-25379-9_11","volume-title":"Certified Programs and Proofs","author":"T. Coquand","year":"2011","unstructured":"Coquand, T., Siles, V.: A Decision Procedure for Regular Expression Equivalence in Type Theory. In: Jouannaud, J.-P., Shao, Z. (eds.) CPP 2011. LNCS, vol.\u00a07086, pp. 119\u2013134. Springer, Heidelberg (2011)"},{"issue":"4","key":"7_CR18","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1145\/321239.321249","volume":"11","author":"J.A. Brzozowski","year":"1964","unstructured":"Brzozowski, J.A.: Derivatives of regular expressions. JACM\u00a011(4), 481\u2013494 (1964)","journal-title":"JACM"},{"issue":"1","key":"7_CR19","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/s10817-011-9223-4","volume":"49","author":"A. Krauss","year":"2012","unstructured":"Krauss, A., Nipkow, T.: Proof pearl: Regular expression equivalence and relation algebra. J. Autom. Reasoning\u00a049(1), 95\u2013106 (2012)","journal-title":"J. Autom. Reasoning"},{"key":"7_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/BFb0055624","volume-title":"CONCUR \u201998 Concurrency Theory","author":"J.J.M.M. Rutten","year":"1998","unstructured":"Rutten, J.J.M.M.: Automata and Coinduction (An Exercise in Coalgebra). In: Sangiorgi, D., de Simone, R. (eds.) CONCUR 1998. LNCS, vol.\u00a01466, pp. 194\u2013218. Springer, Heidelberg (1998)"},{"key":"7_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-45949-9","volume-title":"Isabelle\/HOL","author":"T. Nipkow","year":"2002","unstructured":"Nipkow, T., Paulson, L.C., Wenzel, M.: Isabelle\/HOL. LNCS, vol.\u00a02283. Springer, Heidelberg (2002)"},{"key":"7_CR22","doi-asserted-by":"crossref","unstructured":"Komendantsky, V.: Reflexive toolbox for regular expression matching: verification of functional programs in Coq+Ssreflect. In: Claessen, K., Swamy, N. (eds.) PLPV, pp. 61\u201370. ACM (2012)","DOI":"10.1145\/2103776.2103784"},{"key":"7_CR23","unstructured":"Komendantsky, V.: Computable partial derivatives of regular expressions (2011), http:\/\/www.cs.st-andrews.ac.uk\/~vk\/papers.html (access date: July 1, 2011)"},{"key":"7_CR24","first-page":"110","volume":"5","author":"B. Mirkin","year":"1966","unstructured":"Mirkin, B.: An algorithm for constructing a base in a language of regular expressions. Engineering Cybernetics\u00a05, 110\u2013116 (1966)","journal-title":"Engineering Cybernetics"},{"key":"7_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/978-3-642-32347-8_19","volume-title":"Interactive Theorem Proving","author":"A. Asperti","year":"2012","unstructured":"Asperti, A.: A Compact Proof of Decidability for Regular Expression Equivalence. In: Beringer, L., Felty, A. (eds.) ITP 2012. LNCS, vol.\u00a07406, pp. 283\u2013298. Springer, Heidelberg (2012)"},{"key":"7_CR26","unstructured":"Moreira, N., Pereira, D., Melo de Sousa, S.: Deciding KAT terms equivalence in Coq. Technical Report DCC-2012-04, DCC-FC & LIACC, Universidade do Porto (2012)"},{"key":"7_CR27","unstructured":"Hopcroft, J., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison Wesley (2000)"},{"issue":"3","key":"7_CR28","doi-asserted-by":"crossref","first-page":"195","DOI":"10.3233\/FUN-2001-45303","volume":"45","author":"J.M. Champarnaud","year":"2001","unstructured":"Champarnaud, J.M., Ziadi, D.: From Mirkin\u2019s prebases to Antimirov\u2019s word partial derivatives. Fundam. Inform.\u00a045(3), 195\u2013205 (2001)","journal-title":"Fundam. Inform."},{"key":"7_CR29","unstructured":"Moreira, N., Pereira, D., Melo de Sousa, S.: Coq library: PDCoq (Version 1.1 2012), http:\/\/www.liacc.up.pt\/~kat\/pdcoq\/"},{"key":"7_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1007\/BFb0037116","volume-title":"Typed Lambda Calculi and Applications","author":"C. Paulin-Mohring","year":"1993","unstructured":"Paulin-Mohring, C.: Inductive Definitions in the System Coq: Rules and Properties. In: Bezem, M., Groote, J.F. (eds.) TLCA 1993. LNCS, vol.\u00a0664, pp. 328\u2013345. Springer, Heidelberg (1993)"},{"key":"7_CR31","unstructured":"The Coq Development Team: The Coq proof assistant, http:\/\/coq.inria.fr"},{"key":"7_CR32","first-page":"87","volume":"9","author":"S. Lescuyer","year":"2011","unstructured":"Lescuyer, S.: First-class containers in Coq. Studia Informatica Universalis\u00a09, 87\u2013127 (2011)","journal-title":"Studia Informatica Universalis"},{"key":"7_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/3-540-45685-6_4","volume-title":"Theorem Proving in Higher Order Logics","author":"G. Barthe","year":"2002","unstructured":"Barthe, G., Courtieu, P.: Efficient Reasoning about Executable Specifications in Coq. In: Carre\u00f1o, V.A., Mu\u00f1oz, C., Tahar, S. (eds.) TPHOLs 2002. LNCS, vol.\u00a02410, pp. 31\u201346. Springer, Heidelberg (2002)"},{"key":"7_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/978-3-642-02979-0_10","volume-title":"Implementation and Application of Automata","author":"A. Almeida","year":"2009","unstructured":"Almeida, A., Almeida, M., Alves, J., Moreira, N., Reis, R.: FAdo and GUItar: Tools for Automata Manipulation and Visualization. In: Maneth, S. (ed.) CIAA 2009. LNCS, vol.\u00a05642, pp. 65\u201374. Springer, Heidelberg (2009)"},{"issue":"1","key":"7_CR35","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1145\/343369.343378","volume":"1","author":"D. Kozen","year":"2000","unstructured":"Kozen, D.: On Hoare logic and Kleene algebra with tests. ACM Transactions on Computational Logic (TOCL)\u00a01(1), 60\u201376 (2000)","journal-title":"ACM Transactions on Computational Logic (TOCL)"}],"container-title":["Lecture Notes in Computer Science","Relational and Algebraic Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33314-9_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T08:58:57Z","timestamp":1744102737000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33314-9_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642333132","9783642333149"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33314-9_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}