{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T03:45:49Z","timestamp":1772163949896,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":43,"publisher":"ACM","license":[{"start":{"date-parts":[[2011,1,26]],"date-time":"2011-01-26T00:00:00Z","timestamp":1296000000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2011,1,26]]},"DOI":"10.1145\/1926385.1926429","type":"proceedings-article","created":{"date-parts":[[2011,1,24]],"date-time":"2011-01-24T09:58:22Z","timestamp":1295863102000},"page":"385-398","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Regular expression containment"],"prefix":"10.1145","author":[{"given":"Fritz","family":"Henglein","sequence":"first","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Lasse","family":"Nielsen","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}],"role":[{"role":"author","vocab":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,1,26]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/788018.788829"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/155183.155231"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/647897.740773"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00182-4"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)80010-7"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/876891.880618"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1836089.1836120"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2379036.2379037"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.07.020"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(59)90362-6"},{"key":"e_1_3_2_2_12_1","volume-title":"Regular Algebra and Finite Machines. Printed in GB by William Clowes & Sons Ltd","author":"Conway J. H.","year":"1971","unstructured":"J. H. Conway . Regular Algebra and Finite Machines. Printed in GB by William Clowes & Sons Ltd , 1971 . ISBN 0-412-10620-5. J. H. Conway. Regular Algebra and Finite Machines. Printed in GB by William Clowes & Sons Ltd, 1971. ISBN 0-412-10620-5."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11417170_14"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/982962.964008"},{"key":"e_1_3_2_2_15_1","first-page":"110","volume-title":"Conference version: Proc. 8th Annual IEEE Symp. on Logic in Computer Science (LICS)","author":"Fiore M. P.","year":"1993","unstructured":"M. P. Fiore . A coinduction principle for recursive data types based on bisimulation. Information and Computation, 127: 186--198, 1996 . Conference version: Proc. 8th Annual IEEE Symp. on Logic in Computer Science (LICS) , 1993 , pp. 110 -- 119 . M. P. Fiore. A coinduction principle for recursive data types based on bisimulation. Information and Computation, 127:186--198, 1996. Conference version: Proc. 8th Annual IEEE Symp. on Logic in Computer Science (LICS), 1993, pp. 110--119."},{"key":"e_1_3_2_2_16_1","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1007\/978-3-540-27836-8_53","volume-title":"Proc. 31st International Colloquium on Automata, Languages and Programming (ICALP)","author":"Frisch A.","year":"2004","unstructured":"A. Frisch and L. Cardelli . Greedy regular expression matching . In Proc. 31st International Colloquium on Automata, Languages and Programming (ICALP) , volume 3142 of Lecture notes in computer science , pages 618 -- 629 , Turku, Finland, July 2004 . Springer . A. Frisch and L. Cardelli. Greedy regular expression matching. In Proc. 31st International Colloquium on Automata, Languages and Programming (ICALP), volume 3142 of Lecture notes in computer science, pages 618--629, Turku, Finland, July 2004. Springer."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796802004318"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/321386.321399"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11548133_12"},{"key":"e_1_3_2_2_20_1","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft J.","year":"1979","unstructured":"J. Hopcroft and J. Ullman . Introduction to Automata Theory, Languages, and Computation . Addison-Wesley , 1979 . J. Hopcroft and J. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979."},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1040305.1040310"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1053468.1053470"},{"key":"e_1_3_2_2_23_1","volume-title":"Section 2.8 (Regular expression notation).","author":"Institute of Electrical and Electronics Engineers (IEEE).","year":"1992","unstructured":"Institute of Electrical and Electronics Engineers (IEEE). Standard for information technology---Portable Operating System Interface (POSIX) --- Part 2 (Shell and utilities) , Section 2.8 (Regular expression notation). New York , 1992 . IEEE Standard 1003.2. Institute of Electrical and Electronics Engineers (IEEE). Standard for information technology---Portable Operating System Interface (POSIX) --- Part 2 (Shell and utilities), Section 2.8 (Regular expression notation). New York, 1992. IEEE Standard 1003.2."},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/263699.263763"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1515\/9781400882618-002"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1037"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/256167.256195"},{"key":"e_1_3_2_2_28_1","volume-title":"On the coalgebraic theory of Kleene algebra with tests. Technical report, Computing and Information Science","author":"Kozen D.","year":"2008","unstructured":"D. Kozen . On the coalgebraic theory of Kleene algebra with tests. Technical report, Computing and Information Science , Cornell University , March 2008 . URL http:\/\/hdl.handle.net\/1813\/10173. D. Kozen. On the coalgebraic theory of Kleene algebra with tests. Technical report, Computing and Information Science, Cornell University, March 2008. URL http:\/\/hdl.handle.net\/1813\/10173."},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/158511.158700"},{"key":"e_1_3_2_2_30_1","unstructured":"D.\n      Krob\n    .\n  A complete system of b-rational identities\n  . In M. Paterson editor ICALP volume \n  443\n   of \n  Lecture Notes in Computer Science pages \n  60\n  --\n  73\n  . \n  Springer 1990\n  . ISBN 3-540-52826-1.   D. Krob. A complete system of b-rational identities. In M. Paterson editor ICALP volume 443 of Lecture Notes in Computer Science pages 60--73. Springer 1990. ISBN 3-540-52826-1."},{"key":"e_1_3_2_2_31_1","volume-title":"Proc. Second Asian Symposium, APLAS 2004","volume":"3302","author":"Lu K. Z. M.","year":"2004","unstructured":"K. Z. M. Lu and M. Sulzmann . Rewriting regular inequalities . In Proc. Second Asian Symposium, APLAS 2004 , Taipei, Taiwan , November 4-6, 2004 , volume 3302 of Lecture Notes in Computer Science (LNCS), pages 57--73. Springer, November 2004. K. Z. M. Lu and M. Sulzmann. Rewriting regular inequalities. In Proc. Second Asian Symposium, APLAS 2004, Taipei, Taiwan, November 4-6, 2004, volume 3302 of Lecture Notes in Computer Science (LNCS), pages 57--73. Springer, November 2004."},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90023-0"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/360204.360216"},{"key":"e_1_3_2_2_34_1","volume-title":"DIKU","author":"Nielsen L.","year":"2008","unstructured":"L. Nielsen . A coinductive axiomatization of XML subtyping. Graduate term project report , DIKU , University of Copenhagen , 2008 . L. Nielsen. A coinductive axiomatization of XML subtyping. Graduate term project report, DIKU, University of Copenhagen, 2008."},{"key":"e_1_3_2_2_35_1","volume-title":"Proc. Logics in AI: European Workshop JELIA","volume":"478","author":"Pratt V.","year":"1990","unstructured":"V. Pratt . Action logic and pure induction . In Proc. Logics in AI: European Workshop JELIA , volume 478 of Lecture Notes in Computer Science (LNCS), pages 97--120. Springer , 1990 . V. Pratt. Action logic and pure induction. In Proc. Logics in AI: European Workshop JELIA, volume 478 of Lecture Notes in Computer Science (LNCS), pages 97--120. Springer, 1990."},{"key":"e_1_3_2_2_36_1","volume-title":"Proc. International Joint Conference on Automated Reasoning","author":"Rosu G.","year":"2000","unstructured":"G. Rosu and J. Goguen . Circular coinduction . In Proc. International Joint Conference on Automated Reasoning , 2000 . G. Rosu and J. Goguen. Circular coinduction. In Proc. International Joint Conference on Automated Reasoning, 2000."},{"key":"e_1_3_2_2_37_1","first-page":"127 03740","volume-title":"Proc. 3rd Conference on Algebra and Coalgebra in Computer Science (CALCO), number 5728 in Lecture Notes in Computer Science (LNCS)","author":"Rosu G.","year":"2009","unstructured":"G. Rosu and D. Lucanu . Circular coinduction: A proof theoretical foundation . In Proc. 3rd Conference on Algebra and Coalgebra in Computer Science (CALCO), number 5728 in Lecture Notes in Computer Science (LNCS) , pages 127 -- 144 . Springer , September 2009 . ISBN 978-3-642- 03740 - 03745 . G. Rosu and D. Lucanu. Circular coinduction: A proof theoretical foundation. In Proc. 3rd Conference on Algebra and Coalgebra in Computer Science (CALCO), number 5728 in Lecture Notes in Computer Science (LNCS), pages 127--144. Springer, September 2009. ISBN 978-3-642-03740-5."},{"key":"e_1_3_2_2_38_1","unstructured":"J. J. M. M.\n      Rutten\n    .\n  Automata and coinduction (an exercise in coalgebra)\n  . In D. Sangiorgi and R. de Simone editors CONCUR volume \n  1466\n   of \n  Lecture Notes in Computer Science pages \n  194\n  --\n  218\n  . \n  Springer 1998\n  . ISBN 3-540-64896-8.   J. J. M. M. Rutten. Automata and coinduction (an exercise in coalgebra). In D. Sangiorgi and R. de Simone editors CONCUR volume 1466 of Lecture Notes in Computer Science pages 194--218. Springer 1998. ISBN 3-540-64896-8."},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/321312.321326"},{"key":"e_1_3_2_2_40_1","unstructured":"J. Seward. Bzip. URL http:\/\/www.bzip.org\/.  J. Seward. Bzip. URL http:\/\/www.bzip.org\/."},{"key":"e_1_3_2_2_41_1","volume-title":"Non-deterministic Kleene coalgebras. Logical Methods in Computer Science, 6(3)","author":"Silva A.","year":"2010","unstructured":"A. Silva , M. M. Bonsangue , and J. J. M. M. Rutten . Non-deterministic Kleene coalgebras. Logical Methods in Computer Science, 6(3) , 2010 . URL http:\/\/arxiv.org\/abs\/1007.3769. A. Silva, M. M. Bonsangue, and J. J. M. M. Rutten. Non-deterministic Kleene coalgebras. Logical Methods in Computer Science, 6(3), 2010. URL http:\/\/arxiv.org\/abs\/1007.3769."},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85373-2_5"},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/151145"}],"event":{"name":"POPL '11: The 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages","location":"Austin Texas USA","acronym":"POPL '11","sponsor":["SIGPLAN ACM Special Interest Group on Programming Languages","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1926385.1926429","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1926385.1926429","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:59:51Z","timestamp":1750229991000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1926385.1926429"}},"subtitle":["coinductive axiomatization and computational interpretation"],"short-title":[],"issued":{"date-parts":[[2011,1,26]]},"references-count":43,"alternative-id":["10.1145\/1926385.1926429","10.1145\/1926385"],"URL":"https:\/\/doi.org\/10.1145\/1926385.1926429","relation":{"is-identical-to":[{"id-type":"doi","id":"10.1145\/1925844.1926429","asserted-by":"object"}]},"subject":[],"published":{"date-parts":[[2011,1,26]]},"assertion":[{"value":"2011-01-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}