The Library
Re-pairing brackets
Tools
Chistikov, Dmitry and Vyalyi, Mikhail (2020) Re-pairing brackets. In: The 35th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2020), 8-11 Jul 2020. Published in: LICS '20: Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science pp. 312-326. ISBN 9781450371049. doi:10.1145/3373718.3394752
|
PDF
WRAP-re-pairing-brackets-Chistikov-2020.pdf - Accepted Version - Requires a PDF viewer. Download (1169Kb) | Preview |
Official URL: http://dx.doi.org/10.1145/3373718.3394752
Abstract
Consider the following one-player game. Take a well-formed sequence of opening and closing brackets (a Dyck word). As a move, the player can pair any opening bracket with any closing bracket to its right, erasing them. The goal is to re-pair (erase) the entire sequence, and the cost of a strategy is measured by its width: the maximum number of nonempty segments of symbols (separated by blank space) seen during the play.
For various initial sequences, we prove upper and lower bounds on the minimum width sufficient for re-pairing. (In particular, the sequence associated with the complete binary tree of height n admits a strategy of width sub-exponential in log n.) Our two key contributions are (1) lower bounds on the width and (2) their application in automata theory: quasi-polynomial lower bounds on the translation from one-counter automata to Parikh-equivalent nondeterministic finite automata. The latter result answers a question by Atig et al. (2016).
Item Type: | Conference Item (Paper) | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||
Library of Congress Subject Headings (LCSH): | Machine theory, Formal languages, Combinatorial analysis , Computational complexity | ||||||||||||
Journal or Publication Title: | LICS '20: Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science | ||||||||||||
Publisher: | ACM | ||||||||||||
ISBN: | 9781450371049 | ||||||||||||
Book Title: | Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science | ||||||||||||
Official Date: | 8 July 2020 | ||||||||||||
Dates: |
|
||||||||||||
Page Range: | pp. 312-326 | ||||||||||||
DOI: | 10.1145/3373718.3394752 | ||||||||||||
Status: | Peer Reviewed | ||||||||||||
Publication Status: | Published | ||||||||||||
Reuse Statement (publisher, data, author rights): | © 2020 Copyright held by the owner/author(s). Publication rights licensed to ACM. This is the author’s version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS ’20), July 8–11, 2020, Saarbrücken, Germany, https://doi.org/10. 1145/3373718.3394752. | ||||||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||||||
Date of first compliant deposit: | 10 June 2020 | ||||||||||||
Date of first compliant Open Access: | 10 June 2020 | ||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||
Conference Paper Type: | Paper | ||||||||||||
Title of Event: | The 35th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2020) | ||||||||||||
Type of Event: | Conference | ||||||||||||
Date(s) of Event: | 8-11 Jul 2020 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year