Message 382604 - Python tracker

➜

This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author	ronaldoussoren
Recipients	ammar2, boris, ezio.melotti, mrabarnett, ronaldoussoren, serhiy.storchaka
Date	2020-12-06.19:57:26
SpamBayes Score	-1.0
Marked as misclassified	Yes
Message-id	<1607284646.15.0.889147986649.issue38660@roundup.psfhosted.org>
In-reply-to

Content
https://math.stackexchange.com/questions/46975/how-to-prove-two-regular-expressions-are-identical-in-mathematical-way contains some references to proofs that checking if two regular expressions are equivalent is PSPACE-complete. Another answer in that question mentions that its at least exponential in both space and time. Either means that comparing two REs gets infeasible very fast, which makes this unsuited for an equality checking. I propose closing this issue.

https://math.stackexchange.com/questions/46975/how-to-prove-two-regular-expressions-are-identical-in-mathematical-way contains some references to proofs that checking if two regular expressions are equivalent is PSPACE-complete.  Another answer in that question mentions that its at least exponential in both space and time.  Either means that comparing two REs gets infeasible very fast, which makes this unsuited for an equality checking.

I propose closing this issue.

History
Date	User	Action	Args
2020-12-06 19:57:26	ronaldoussoren	set	recipients: + ronaldoussoren, ezio.melotti, mrabarnett, serhiy.storchaka, ammar2, boris
2020-12-06 19:57:26	ronaldoussoren	set	messageid: <1607284646.15.0.889147986649.issue38660@roundup.psfhosted.org>
2020-12-06 19:57:26	ronaldoussoren	link	issue38660 messages
2020-12-06 19:57:26	ronaldoussoren	create