A decision problem about balanced parentheses
José Manuel Rodríguez Caballero
josephcmac at gmail.com
Tue Mar 17 03:11:16 EDT 2020
Dear FOM members,
I would like to ask for any reference concerning the following problem or
any variation of it.
Given a list of balanced parentheses L, is there a proof in first-order
Peano arithmetic that we are in either of the following cases:
A. there is a positive integer n such that L is equal to Dyck(n),
B. for any positive integer n we have that L is not equal to Dyck(n),
where Dyck(n) is given by the following algorithm:
Input: a positive integer n.
Step 1. Write the divisors of 2n in increasing order.
Step 2. Delete the divisors d such that both d and 2n divided by d are even
Step 3. For any odd number in the list, write an open parenthesis and for
any even number, write a close parenthesis.
Output: the list of parentheses, denoted Dyck(n).
Input n = 30.
1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60
1, 3, 4, 5, 12, 15, 20, 60
Step 3 (output).
Dyck(30) is ( ( ) ( ) ( ) )
In the case of the list L given by ( ( ) ( ) ( ) ), we are in case A. For
the list L given by ( ) ( ( ( ) ) ) we are in case B.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the FOM