{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:45:06Z","timestamp":1775054706381,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":51,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,7,8]],"date-time":"2020-07-08T00:00:00Z","timestamp":1594166400000},"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":[[2020,7,8]]},"DOI":"10.1145\/3373718.3394752","type":"proceedings-article","created":{"date-parts":[[2020,5,26]],"date-time":"2020-05-26T00:23:18Z","timestamp":1590452598000},"page":"312-326","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Re-pairing brackets"],"prefix":"10.1145","author":[{"given":"Dmitry","family":"Chistikov","sequence":"first","affiliation":[{"name":"Centre for Discrete Mathematics and its Applications (DIMAP), Department of Computer Science, University of Warwick, Coventry, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikhail","family":"Vyalyi","sequence":"additional","affiliation":[{"name":"National Research University Higher School of Economics, Moscow, Russia, Dorodnicyn Computing Centre, FRC CSC RAS, Moscow, Russia, Moscow Institute of Physics and Technology, Dolgoprudny, Moscow Region, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,7,8]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Roland Meyer, and Mehdi Seyed Salehi.","author":"Abdulla Parosh Aziz","year":"2015","unstructured":"Parosh Aziz Abdulla , Mohamed Faouzi Atig , Roland Meyer, and Mehdi Seyed Salehi. 2015 . What's Decidable about Availability Languages?. In FSTTCS'15 (LIPIcs) , Vol. 45 . 192--205. Parosh Aziz Abdulla, Mohamed Faouzi Atig, Roland Meyer, and Mehdi Seyed Salehi. 2015. What's Decidable about Availability Languages?. In FSTTCS'15 (LIPIcs), Vol. 45. 192--205."},{"key":"e_1_3_2_1_2_1","first-page":"61","article-title":"Some questions of phrase-structure grammars I","volume":"4","author":"Abraham Samuel","year":"1965","unstructured":"Samuel Abraham . 1965 . Some questions of phrase-structure grammars I . Computational Linguistics 4 (1965), 61 -- 70 . Samuel Abraham. 1965. Some questions of phrase-structure grammars I. Computational Linguistics 4 (1965), 61--70.","journal-title":"Computational Linguistics"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Martin Aigner and G\u00fcnter M. Ziegler (Eds.). 2009. Proofs from THE BOOK. Springer.  Martin Aigner and G\u00fcnter M. Ziegler (Eds.). 2009. Proofs from THE BOOK. Springer.","DOI":"10.1007\/978-3-642-00856-6"},{"key":"e_1_3_2_1_4_1","volume-title":"FSTTCS'10","author":"Alur Rajeev","year":"2010","unstructured":"Rajeev Alur and Pavol Cern\u00fd . 2010 . Expressiveness of streaming string transducers . In FSTTCS'10 . 1--12. Rajeev Alur and Pavol Cern\u00fd. 2010. Expressiveness of streaming string transducers. In FSTTCS'10. 1--12."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926454"},{"key":"e_1_3_2_1_6_1","volume-title":"Decision Problems for Additive Regular Functions. In ICALP'13 (Proceedings, Part II). 37--48","author":"Alur Rajeev","year":"2013","unstructured":"Rajeev Alur and Mukund Raghothaman . 2013 . Decision Problems for Additive Regular Functions. In ICALP'13 (Proceedings, Part II). 37--48 . Rajeev Alur and Mukund Raghothaman. 2013. Decision Problems for Additive Regular Functions. In ICALP'13 (Proceedings, Part II). 37--48."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2934561"},{"key":"e_1_3_2_1_8_1","volume-title":"Minimizing Resources of Sweeping and Streaming String Transducers. In ICALP'16","author":"Baschenis F\u00e9lix","year":"2016","unstructured":"F\u00e9lix Baschenis , Olivier Gauwin , Anca Muscholl , and Gabriele Puppis . 2016 . Minimizing Resources of Sweeping and Streaming String Transducers. In ICALP'16 . 114:1--114:14. F\u00e9lix Baschenis, Olivier Gauwin, Anca Muscholl, and Gabriele Puppis. 2016. Minimizing Resources of Sweeping and Streaming String Transducers. In ICALP'16. 114:1--114:14."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)90771-1"},{"key":"e_1_3_2_1_10_1","unstructured":"Dmitry Chistikov and Mikhail Vyalyi. 2019. Re-pairing brackets. https:\/\/arxiv.org\/abs\/1904.08402 arXiv:1904.08402 [cs.FL].  Dmitry Chistikov and Mikhail Vyalyi. 2019. Re-pairing brackets. https:\/\/arxiv.org\/abs\/1904.08402 arXiv:1904.08402 [cs.FL]."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80048-7"},{"key":"e_1_3_2_1_12_1","volume-title":"Handbook of Formal Languages","author":"Dassow J\u00fcrgen","unstructured":"J\u00fcrgen Dassow , Gheorghe P\u0103un , and Arto Salomaa . 1997. Grammars with Controlled Derivations . In Handbook of Formal Languages , Volume 2 . Linear Modeling : Background and Application. Springer , 101--154. J\u00fcrgen Dassow, Gheorghe P\u0103un, and Arto Salomaa. 1997. Grammars with Controlled Derivations. In Handbook of Formal Languages, Volume 2. Linear Modeling: Background and Application. Springer, 101--154."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2934549"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/371316.371512"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/263139.263146"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.03.019"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629644"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-04921-2_1"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2984450.2984453"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2160910.2160915"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(68)80009-1"},{"key":"e_1_3_2_1_22_1","first-page":"363","volume-title":"Finding Lower Bounds for Nondeterministic State Complexity is Hard. Electronic Colloquium on Computational Complexity (ECCC) 13, 027","author":"Gruber Hermann","year":"2006","unstructured":"Hermann Gruber and Markus Holzer . 2006. Finding Lower Bounds for Nondeterministic State Complexity is Hard. Electronic Colloquium on Computational Complexity (ECCC) 13, 027 ( 2006 ). Conference version in: Developments in Language Theory (DLT) 2006; Lecture Notes in Computer Science, vol. 4036 , pp. 363 -- 374 , Springer . Hermann Gruber and Markus Holzer. 2006. Finding Lower Bounds for Nondeterministic State Complexity is Hard. Electronic Colloquium on Computational Complexity (ECCC) 13, 027 (2006). Conference version in: Developments in Language Theory (DLT) 2006; Lecture Notes in Computer Science, vol. 4036, pp. 363--374, Springer."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(71)90095-7"},{"key":"e_1_3_2_1_24_1","volume-title":"STACS (LIPIcs)","volume":"47","author":"Haase Christoph","year":"2016","unstructured":"Christoph Haase and Piotr Hofman . 2016 . Tightening the Complexity of Equivalence Problems for Commutative Grammars . In STACS (LIPIcs) , Vol. 47 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 41:1--41:14. Christoph Haase and Piotr Hofman. 2016. Tightening the Complexity of Equivalence Problems for Commutative Grammars. In STACS (LIPIcs), Vol. 47. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 41:1--41:14."},{"key":"e_1_3_2_1_25_1","volume-title":"CAV (Lecture Notes in Computer Science)","author":"Hague Matthew","unstructured":"Matthew Hague and Anthony Widjaja Lin . 2012. Synchronisation- and Reversal-Bounded Analysis of Multithreaded Programs with Counters . In CAV (Lecture Notes in Computer Science) , Vol. 7358 . Springer , 260--276. Matthew Hague and Anthony Widjaja Lin. 2012. Synchronisation- and Reversal-Bounded Analysis of Multithreaded Programs with Counters. In CAV (Lecture Notes in Computer Science), Vol. 7358. Springer, 260--276."},{"key":"e_1_3_2_1_26_1","volume-title":"CONCUR (Lecture Notes in Computer Science)","author":"Hoenicke Jochen","unstructured":"Jochen Hoenicke , Roland Meyer , and Ernst-R\u00fcdiger Olderog . 2010. Kleene, Rabin, and Scott Are Available . In CONCUR (Lecture Notes in Computer Science) , Vol. 6269 . Springer , 462--477. Jochen Hoenicke, Roland Meyer, and Ernst-R\u00fcdiger Olderog. 2010. Kleene, Rabin, and Scott Are Available. In CONCUR (Lecture Notes in Computer Science), Vol. 6269. Springer, 462--477."},{"key":"e_1_3_2_1_27_1","volume-title":"Nondeterministic Finite Automata-Recent Results on the Descriptional and Computational Complexity. In CIAA'08","author":"Holzer Markus","year":"2008","unstructured":"Markus Holzer and Martin Kutrib . 2008 . Nondeterministic Finite Automata-Recent Results on the Descriptional and Computational Complexity. In CIAA'08 . 1--16. Markus Holzer and Martin Kutrib. 2008. Nondeterministic Finite Automata-Recent Results on the Descriptional and Computational Complexity. In CIAA'08. 1--16."},{"key":"e_1_3_2_1_28_1","volume-title":"Communication Complexity and Parallel Computing","author":"Hromkovic Juraj","unstructured":"Juraj Hromkovic . 1997. Communication Complexity and Parallel Computing . Springer . Juraj Hromkovic. 1997. Communication Complexity and Parallel Computing. Springer."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.03.020"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(83)80022-9"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80015-2"},{"key":"e_1_3_2_1_32_1","volume-title":"Complexity of Problems of Commutative Grammars. Logical Methods in Computer Science 11, 1","author":"Kopczynski Eryk","year":"2015","unstructured":"Eryk Kopczynski . 2015. Complexity of Problems of Commutative Grammars. Logical Methods in Computer Science 11, 1 ( 2015 ). Eryk Kopczynski. 2015. Complexity of Problems of Commutative Grammars. Logical Methods in Computer Science 11, 1 (2015)."},{"key":"e_1_3_2_1_33_1","volume-title":"Parikh Images of Grammars: Complexity and Applications","author":"Kopczynski Eryk","unstructured":"Eryk Kopczynski and Anthony Widjaja To. 2010. Parikh Images of Grammars: Complexity and Applications . In LICS. IEEE Computer Society , 80--89. Eryk Kopczynski and Anthony Widjaja To. 2010. Parikh Images of Grammars: Complexity and Applications. In LICS. IEEE Computer Society, 80--89."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(79)90641-7"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(80)90136-2"},{"key":"e_1_3_2_1_36_1","volume-title":"The space complexity of two pebble games on trees. Technical memorandum TM-133. Laboratory for Computer Science","author":"Loui Michael Conrad","unstructured":"Michael Conrad Loui . 1979. The space complexity of two pebble games on trees. Technical memorandum TM-133. Laboratory for Computer Science , Massachusetts Institute of Technology (MIT) . Michael Conrad Loui. 1979. The space complexity of two pebble games on trees. Technical memorandum TM-133. Laboratory for Computer Science, Massachusetts Institute of Technology (MIT)."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(81)80004-7"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-55751-8_3"},{"key":"e_1_3_2_1_39_1","volume-title":"STACS (LIPIcs)","volume":"126","author":"Muscholl Anca","year":"2019","unstructured":"Anca Muscholl and Gabriele Puppis . 2019 . The Many Facets of String Transducers (Invited Talk) . In STACS (LIPIcs) , Vol. 126 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2:1--2:21. Anca Muscholl and Gabriele Puppis. 2019. The Many Facets of String Transducers (Invited Talk). In STACS (LIPIcs), Vol. 126. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2:1--2:21."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_3_2_1_41_1","volume-title":"Logical Methods in Computer Science","author":"Nordstr\u00f6m Jakob","year":"2013","unstructured":"Jakob Nordstr\u00f6m . 2013. Pebble Games , Proof Complexity , and Time-Space Trade-offs. Logical Methods in Computer Science Volume 9 , Issue 3 ( Sept. 2013 ), 1--63. Jakob Nordstr\u00f6m. 2013. Pebble Games, Proof Complexity, and Time-Space Trade-offs. Logical Methods in Computer Science Volume 9, Issue 3 (Sept. 2013), 1--63."},{"key":"e_1_3_2_1_42_1","unstructured":"Jakob Nordstr\u00f6m. 2015. New Wine into Old Wineskins: A Survey of Some Pebbling Classics with Supplemental Results. http:\/\/csc.kth.se\/~jakobn\/research\/PebblingSurveyTMP.pdf Available at http:\/\/csc.kth.se\/~jakobn\/research\/PebblingSurveyTMP.pdf.  Jakob Nordstr\u00f6m. 2015. New Wine into Old Wineskins: A Survey of Some Pebbling Classics with Supplemental Results. http:\/\/csc.kth.se\/~jakobn\/research\/PebblingSurveyTMP.pdf Available at http:\/\/csc.kth.se\/~jakobn\/research\/PebblingSurveyTMP.pdf."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/321356.321364"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(72)80025-4"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0028821"},{"key":"e_1_3_2_1_46_1","first-page":"221","article-title":"Outils et R\u00e9sultats Pour Les Transducteurs Boustrophedons","volume":"20","author":"Rozoy Brigitte","year":"1986","unstructured":"Brigitte Rozoy . 1986 . Outils et R\u00e9sultats Pour Les Transducteurs Boustrophedons . ITA 20 , 3 (1986), 221 -- 249 . Brigitte Rozoy. 1986. Outils et R\u00e9sultats Pour Les Transducteurs Boustrophedons. ITA 20, 3 (1986), 221--249.","journal-title":"ITA"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90012-5"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(69)90164-8"},{"key":"e_1_3_2_1_49_1","volume-title":"Models of Computation: Exploring the Power of Computing","author":"Savage John E.","unstructured":"John E. Savage . 1998. Models of Computation: Exploring the Power of Computing . Addison-Wesley . http:\/\/cs.brown.edu\/people\/jsavage\/book\/ John E. Savage. 1998. Models of Computation: Exploring the Power of Computing. Addison-Wesley. http:\/\/cs.brown.edu\/people\/jsavage\/book\/"},{"key":"e_1_3_2_1_50_1","volume-title":"Combinatorial optimization","author":"Schrijver Alexander","unstructured":"Alexander Schrijver . 2003. Combinatorial optimization . Springer-Verlag . Alexander Schrijver. 2003. Combinatorial optimization. Springer-Verlag."},{"key":"e_1_3_2_1_51_1","volume-title":"A Second Course in Formal Languages and Automata Theory","author":"Shallit Jeffrey","unstructured":"Jeffrey Shallit . 2009. A Second Course in Formal Languages and Automata Theory . Cambridge University Press . Jeffrey Shallit. 2009. A Second Course in Formal Languages and Automata Theory. Cambridge University Press."}],"event":{"name":"LICS '20: 35th Annual ACM\/IEEE Symposium on Logic in Computer Science","location":"Saarbr\u00fccken Germany","acronym":"LICS '20","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation","EACSL European Association for Computer Science Logic","IEEE-CS\\DATC IEEE Computer Society"]},"container-title":["Proceedings of the 35th Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3373718.3394752","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3373718.3394752","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:35Z","timestamp":1750197755000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3373718.3394752"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,8]]},"references-count":51,"alternative-id":["10.1145\/3373718.3394752","10.1145\/3373718"],"URL":"https:\/\/doi.org\/10.1145\/3373718.3394752","relation":{},"subject":[],"published":{"date-parts":[[2020,7,8]]},"assertion":[{"value":"2020-07-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}