coq-community / reglang

Regular Language Representations in Coq [maintainers=@chdoc,@palmskog]

Regular Language Representations in Coq

This library provides definitions and verified translations between different representations of regular languages: various forms of automata (deterministic, nondeterministic, one-way, two-way), regular expressions, and the logic WS1S. It also contains various decidability results and closure properties of regular languages.

Meta

• Author(s):
  • Christian Doczkal (initial)
  • Jan-Oliver Kaiser (initial)
  • Gert Smolka (initial)
• Coq-community maintainer(s):
  • Christian Doczkal (@chdoc)
  • Karl Palmskog (@palmskog)
• License: CeCILL-B
• Compatible Coq versions: 8.16 or later (use releases for other Coq versions)
• Additional dependencies:
  • MathComp 2.0 or later (ssreflect suffices)
  • Hierarchy Builder 1.4.0 or later
• Coq namespace: RegLang
• Related publication(s):
  • Regular Language Representations in the Constructive Type Theory of Coq doi:10.1007/s10817-018-9460-x

Building and installation instructions

The easiest way to install the latest released version of Regular Language Representations in Coq is via OPAM:

opam repo add coq-released https://coq.inria.fr/opam/released
opam install coq-reglang

To instead build and install manually, do:

git clone https://github.com/coq-community/reglang.git
cd reglang
make   # or make -j <number-of-cores-on-your-machine> 
make install

HTML Documentation

To generate HTML documentation, run make coqdoc and point your browser at docs/coqdoc/toc.html.

See also the pregenerated HTML documentation for the latest release.

File Contents

• misc.v, setoid_leq.v: basic infrastructure independent of regular languages
• languages.v: languages and decidable languages
• dfa.v:
  • results on deterministic one-way automata
  • definition of regularity
  • criteria for nonregularity
• nfa.v: Results on nondeterministic one-way automata
• regexp.v: Regular expressions and Kleene Theorem
• minimization.v: minimization and uniqueness of minimal DFAs
• myhill_nerode.v: classifiers and the constructive Myhill-Nerode theorem
• two_way.v: deterministic and nondeterministic two-way automata
• vardi.v: translation from 2NFAs to NFAs for the complement language
• shepherdson.v: translation from 2NFAs and 2DFAs to DFAs (via classifiers)
• wmso.v:
  • decidability of WS1S
  • WS1S as representation of regular languages

reglang's Issues

Support mathcomp 2

There's both a porting guide and a PR. And I can confirm the PR patch makes things compile - with many warnings, but it compiles.

Release 1.1.3

I propose that for the Coq platform release with Coq 8.15, we make RegLang release 1.1.3 that supports MathComp 1.11 or later (i.e., including content of #37). This release can then be the basis of a release of Regexp Brzozowski, which was recently ported to use RegLang. I'm opening this issue as a memento.

release 1.1.1

@palmskog Should we make a maintenance release to make #17 and #18 available to users (in particular of the coq platform)? If there is nothing else you want to add, I would tag the current master as v1.1.1.

Can we build with dune?

Hi. Can we build this library with dune?

dune build gave me this error:

$ dune build
Warning: Coq Language Versions lower than 0.8 have been deprecated in Dune
3.8 and will be removed in an upcoming Dune version.
File "./theories/misc.v", line 99, characters 52-57:
Error:
In environment
T : finType
p : pred T
eq_pT : #|{: {x : T | p x}}| = #|T|
The term "{x : T | p x}" has type "Type" while it is expected to have type
 "finType".

Yet, I could step through the whole of misc.v without error in my text editor.

Software versions:

• dune: 3.11.1
• Coq: 8.18.0
• mathcomp: 2.2.0 (build from source)
• reglang: 1.2.1

Does _CoqProject file play a role here?

Building with make worked smoothly though.

Replace omega with lia

Coq-8.13 will (hopefully) come with a lia tactic that can natively deal with boolean operators and relations (PR #11906). This might allow getting rid of omega without having to use manual reflection.

Please pick the version you prefer for Coq 8.18 in Coq Platform 2023.10

The Coq team released Coq 8.18.0 on September 7th, 2023.
The corresponding Coq Platform release 2023.10 should be released before November 30th, 2023.
It can be delayed in case of difficulties until January 15th, 2023, but this should be an exception.

This issue is to inform you that the opam package we are currently testing in Coq Platform CI works fine with Coq 8.18.0.

Coq Platform CI is currently testing opam package coq-reglang.1.2.0
from official repository https://coq.inria.fr/opam/released/packages/coq-reglang/coq-reglang.1.2.0/opam.

In case this is the version you want to see in Coq Platform, there is nothing to do for you - please just close this issue.

In case you would prefer to see an updated or an older version in the upcoming Coq Platform 2023.10, please inform us as soon as possible and before October 31st, 2023!

The working branch of Coq Platform, can be found here main.
It contains package pick ~8.18+beta1 which already supports Coq version 8.18.0 and contains already working (possibly patched / commit pinned) Coq Platform packages.

In case you want to select a different version, please don't close this issue, even after creating the new tag and/or opam package.
We will close the issue after updating Coq Platform.
This is a measure of 'double book keeping' in order to avoid that we ship the wrong version.

In any case, Coq Platform won't be released before this issue is closed!

Thanks!

P.S.: this issue has been created automatically based on CI status.

CC: coq/platform#372

Deploying HTML documentation (website)

As per #7, we can use the gh-pages branch of the repo to deploy static HTML, which will then appear at the URL https://coq-community.github.io/reglang

If this is done for every revision (i.e., new documentation deployment), the repo can grow to the point of becoming very inconvenient to clone, which has happened to https://github.com/HoTT/HoTT

Hence, the compromise we use in coq-community is to advocate deployment of documentation only for releases of a project, or putting documentation in a separate repo. Here is one example of a landing page: https://coq-community.github.io/lemma-overloading/

Any preferences here @chdoc, is the standard landing page OK with you?

Please pick the version you prefer for Coq 8.14 in Coq Platform 2021.11

The Coq team released Coq 8.14+rc1 on September 17, 2021 and plans to release Coq 8.14.0 before October 31, 2021.
The corresponding Coq Platform release 2021.11 should be released before November 30, 2021.
It can be delayed in case of difficulties until January 31, 2022, but this should be an exception.

This issue is to inform you that the opam package we are currently testing in Coq Platform CI works fine with Coq 8.14+rc1.

Coq Platform CI is currently testing opam package coq-reglang.1.1.2
from official repository https://coq.inria.fr/opam/released/packages/coq-reglang/coq-reglang.1.1.2/opam.

In case this is the version you want to see in Coq Platform, there is nothing to do for you - please just close this issue.

In case you would prefer to see an updated or an older version in the upcoming Coq Platform 2021.11, please inform us as soon as possible and before November 15, 2021!

The working branch of Coq Platform, which already supports Coq version 8.14+rc1, can be found here https://github.com/coq/platform/tree/main.

In case you want to select a different version, please don't close this issue, even after creating the new tag and/or opam package.
We will close the issue after updating Coq Platform.
This is a measure of 'double book keeping' in order to avoid that we ship the wrong version.

In any case, Coq Platform won't be released before this issue is closed!

Thanks!

P.S.: this issue has been created automatically based on CI status.

CC: coq/platform#139

Please pick the version you prefer for Coq 8.19 in Coq Platform 2024.01

The Coq team released Coq 8.19.0 on January 24th, 2024.
The corresponding Coq Platform release 2024.01 should be released before April 30th, 2024.
It can be delayed in case of difficulties until May 15th, 2024, but this should be an exception.

This issue is to inform you that the opam package we are currently testing in Coq Platform CI works fine with Coq 8.19.0.

Coq Platform CI is currently testing opam package coq-reglang.1.2.1
from official repository https://coq.inria.fr/opam/released/packages/coq-reglang/coq-reglang.1.2.1/opam.

In case this is the version you want to see in Coq Platform, there is nothing to do for you - please just close this issue.

In case you would prefer to see an updated or an older version in the upcoming Coq Platform 2024.01, please inform us as soon as possible and before March 31st, 2024!

The working branch of Coq Platform, can be found here main.
It contains package pick ~8.19~2024.01+beta1 which already supports Coq version 8.19.0 and contains already working (possibly patched / commit pinned) Coq Platform packages.

In case you want to select a different version, please don't close this issue, even after creating the new tag and/or opam package.
We will close the issue after updating Coq Platform.
This is a measure of 'double book keeping' in order to avoid that we ship the wrong version.

In any case, Coq Platform won't be released before this issue is closed!

Thanks!

P.S.: this issue has been created automatically based on CI status.

CC: coq/platform#405

Please pick the version you prefer for Coq 8.17 in Coq Platform 2023.03

The Coq team released Coq 8.17+rc1 on December 29th, 2022 and plans to release Coq 8.17.0 around March 7th, 2023.
The corresponding Coq Platform release 2023.03 should be released before April 14th, 2023.
It can be delayed in case of difficulties until June 30, 2023, but this should be an exception.

This issue is to inform you that the opam package we are currently testing in Coq Platform CI works fine with Coq 8.17+rc1.

Coq Platform CI is currently testing opam package coq-reglang.1.1.3
from platform patch repository https://github.com/coq/platform/tree/main/opam/opam-coq-archive/released/packages/coq-reglang/coq-reglang.1.1.3/opam. This means we had to weaken some version restrictions in the opam package, but no other changes were required.

In case this is the version you want to see in Coq Platform, there is nothing to do for you - please just close this issue.

In case you would prefer to see an updated or an older version in the upcoming Coq Platform 2023.03, please inform us as soon as possible and before March 21st, 2023!

The working branch of Coq Platform, can be found here main.
It contains package pick ~8.17~2023.03+preview1 which already supports Coq version 8.17+rc1 and contains already working (possibly patched / commit pinned) Coq Platform packages.

In case you want to select a different version, please don't close this issue, even after creating the new tag and/or opam package.
We will close the issue after updating Coq Platform.
This is a measure of 'double book keeping' in order to avoid that we ship the wrong version.

In any case, Coq Platform won't be released before this issue is closed!

Thanks!

P.S.: this issue has been created automatically based on CI status.

CC: coq/platform#335

Please tag a new release with MC 2 support

Debian will release a new stable version tomorrow after months of freeze. As the rolling release will start again, I'll want to update the Coq-related packages - there are two big new toys I would like to ship: coq 8.17 and MC2.

Can you tag a new release with MC2 ?

Thanks

Please pick the version you prefer for Coq 8.15 in Coq Platform 2022.02

The Coq team released Coq 8.15.0 on January 13, 2022.
The corresponding Coq Platform release 2022.02 should be released before February 28, 2022.
It can be delayed in case of difficulties until April 11, 2022, but this should be an exception.

This issue is to inform you that the opam package we are currently testing in Coq Platform CI works fine with Coq 8.15.0.

Coq Platform CI is currently testing opam package coq-reglang.1.1.2
from platform patch repository https://github.com/coq/platform/tree/main/opam/opam-coq-archive/released/packages/coq-reglang/coq-reglang.1.1.2/opam.

In case this is the version you want to see in Coq Platform, there is nothing to do for you - please just close this issue.

In case you would prefer to see an updated or an older version in the upcoming Coq Platform 2022.02, please inform us as soon as possible and before February 14, 2022!

The working branch of Coq Platform, which already supports Coq version 8.15.0, can be found here https://github.com/coq/platform/tree/main.

In case you want to select a different version, please don't close this issue, even after creating the new tag and/or opam package.
We will close the issue after updating Coq Platform.
This is a measure of 'double book keeping' in order to avoid that we ship the wrong version.

In any case, Coq Platform won't be released before this issue is closed!

Thanks!

P.S.: this issue has been created automatically based on CI status.

CC: coq/platform#193

Please pick the version you prefer for Coq 8.16 in Coq Platform 2022.09

The Coq team released Coq 8.16+rc1 on June 01, 2022.
The corresponding Coq Platform release 2022.09 should be released before September 15, 2022.
It can be delayed in case of difficulties until October 15, 2022, but this should be an exception.

This issue is to inform you that the opam package we are currently testing in Coq Platform CI works fine with Coq 8.16+rc1.

Coq Platform CI is currently testing opam package coq-reglang.1.1.3
from platform patch repository https://github.com/coq/platform/tree/main/opam/opam-coq-archive/released/packages/coq-reglang/coq-reglang.1.1.3/opam. This means we had to weaken some version restrictions in the opam package, but no other changes were required.

In case this is the version you want to see in Coq Platform, there is nothing to do for you - please just close this issue.

In case you would prefer to see an updated or an older version in the upcoming Coq Platform 2022.09, please inform us as soon as possible and before August 31, 2022!

The working branch of Coq Platform, can be found here main.
It contains package pick ~8.16+rc1~2022.09~preview1 which already supports Coq version 8.16+rc1 and contains already working (possibly patched / commit pinned) Coq Platform packages.

In case you want to select a different version, please don't close this issue, even after creating the new tag and/or opam package.
We will close the issue after updating Coq Platform.
This is a measure of 'double book keeping' in order to avoid that we ship the wrong version.

In any case, Coq Platform won't be released before this issue is closed!

Thanks!

P.S.: this issue has been created automatically based on CI status.

CC: coq/platform#274

Refinements for performance of extracted code

This is an ongoing effort to document how the executable parts of reglang could be refined to have better performance in practice for extracted code. This kind of refinement could be done in several ways, most directly in the style of CoqEAL.