Abstract Given a string of parentheses, the task is to find the longest consecutive segment that is balanced, in linear time. We find this problem interesting because it involves a combination of techniques: the usual approach for solving segment problems and a theorem for constructing the inverse of a function—through which we derive an instance of shift-reduce parsing.

@article{paperbot1242,
  title = {Longest segment of balanced parentheses: an exercise in program inversion in a segment problem},
  author = {SHIN-CHENG MU and TSUNG-JU CHIANG},
  journal = {Journal of Functional Programming},
  volume = {31},
  year = {2021},
  doi = {10.1017/s0956796821000253}
}