Skip to content

[Merged by Bors] - feat: lower bounds for Levenshtein edit distance#6118

Closed
kim-em wants to merge 30 commits intomasterfrom
edit_distance_bounds
Closed

[Merged by Bors] - feat: lower bounds for Levenshtein edit distance#6118
kim-em wants to merge 30 commits intomasterfrom
edit_distance_bounds

Conversation

@kim-em
Copy link
Copy Markdown
Contributor

@kim-em kim-em commented Jul 25, 2023

@kim-em kim-em added awaiting-review awaiting-CI This PR does not pass CI yet. This label is automatically removed once it does. labels Jul 25, 2023
@ghost ghost added the blocked-by-other-PR This PR depends on another PR (this label is automatically managed by a bot) label Jul 25, 2023
@github-actions github-actions bot removed the awaiting-CI This PR does not pass CI yet. This label is automatically removed once it does. label Jul 25, 2023
@kim-em kim-em added the t-combinatorics Combinatorics label Aug 6, 2023
kim-em and others added 21 commits August 11, 2023 09:47
This PR protects `Function.Commute`, so that it no longer clashes with `Commute` in the root namespace, as suggested by @j-loreaux in #6290.
… ≃ (Aᵐᵒᵖ ≃ₐ[R] B)` (#6525)

This also adds the missing `AlgEquiv.equivCongr` as a more general version of `AlgEquiv.autCongr`.
…ar order (#6571)

Currently, in a conditionally complete linear order, the supremum of an unbounded set hasn't any specific property. However, in all instances in mathlib, all unbounded sets have the same supremum. This PR adds this requirement in mathlib. This will be convenient to remove boundedness assumptions in measurability statements.
The main changes are:

- we replace the data-bearing `PerfectRing` typeclass with a `Prop`-valued (non-constructive) version,
- we introduce a new typeclass `PerfectField`,
- we add a proof that a perfect field of positive characteristic has surjective Frobenius map,
- we add some basic facts such as perfection of finite rings / fields and products of perfect rings.
Removing some linters and error codes that are not Lean 4 relevant



Co-authored-by: Eric Wieser <wieser.eric@gmail.com>
Prove [Gershgorin circle theorem](https://en.wikipedia.org/wiki/Gershgorin_circle_theorem) and some applications that will be useful for the proof of Dirichlet's unit theorem #5960
… identities (#6139)

Co-authored-by: michaellee94 <michael.a.rodrigues.lee@gmail.com>
Co-authored-by: Oliver Nash <github@olivernash.org>
@ghost ghost removed the blocked-by-other-PR This PR depends on another PR (this label is automatically managed by a bot) label Aug 16, 2023
@ghost
Copy link
Copy Markdown

ghost commented Aug 16, 2023

This PR/issue depends on:

@ghost ghost added the merge-conflict The PR has a merge conflict with master, and needs manual merging. (this label is managed by a bot) label Aug 16, 2023
@ghost ghost removed the merge-conflict The PR has a merge conflict with master, and needs manual merging. (this label is managed by a bot) label Aug 16, 2023
Copy link
Copy Markdown
Member

@PatrickMassot PatrickMassot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Some of my suggestion come purely from my reluctance to non-terminal simp only without goal restating, feel free to ignore. Others are simply using that I like named arguments in Lean 4 .

bors d+

@bors
Copy link
Copy Markdown

bors bot commented Aug 29, 2023

✌️ semorrison can now approve this pull request. To approve and merge a pull request, simply reply with bors r+. More detailed instructions are available here.

@ghost ghost added delegated This pull request has been delegated to the PR author (or occasionally another non-maintainer). and removed awaiting-review labels Aug 29, 2023
@kim-em
Copy link
Copy Markdown
Contributor Author

kim-em commented Aug 29, 2023

bors merge

@github-actions github-actions bot added the ready-to-merge This PR has been sent to bors. label Aug 29, 2023
bors bot pushed a commit that referenced this pull request Aug 29, 2023
Co-authored-by: Scott Morrison <scott.morrison@gmail.com>
Co-authored-by: Eric Wieser <wieser.eric@gmail.com>
Co-authored-by: Thomas Browning <tb65536@uw.edu>
Co-authored-by: Chris Hughes <chrishughes24@gmail.com>
Co-authored-by: Oliver Nash <github@olivernash.org>
Co-authored-by: sgouezel <sebastien.gouezel@univ-rennes1.fr>
Co-authored-by: Alex J Best <alex.j.best@gmail.com>
Co-authored-by: Xavier Roblot <46200072+xroblot@users.noreply.github.com>
Co-authored-by: michaellee94 <michael_lee1@brown.edu>
@bors
Copy link
Copy Markdown

bors bot commented Aug 29, 2023

Pull request successfully merged into master.

Build succeeded!

The publicly hosted instance of bors-ng is deprecated and will go away soon.

If you want to self-host your own instance, instructions are here.
For more help, visit the forum.

If you want to switch to GitHub's built-in merge queue, visit their help page.

@bors bors bot changed the title feat: lower bounds for Levenshtein edit distance [Merged by Bors] - feat: lower bounds for Levenshtein edit distance Aug 29, 2023
@bors bors bot closed this Aug 29, 2023
@bors bors bot deleted the edit_distance_bounds branch August 29, 2023 04:51
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

delegated This pull request has been delegated to the PR author (or occasionally another non-maintainer). ready-to-merge This PR has been sent to bors. t-combinatorics Combinatorics

Projects

None yet

Development

Successfully merging this pull request may close these issues.

9 participants