Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.14559 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909848667422720 |
|---|---|
| author | Vágvölgyi, Sándor |
| author_facet | Vágvölgyi, Sándor |
| contents | We show that for any ground term equation systems $E$ and $F$, (1) the union of the generated congruences by $E$ and $F$ is a congruence on the ground term algebra if and only if there exists a ground term equation system $H$ such that the congruence generated by $H$ is equal to the union of the congruences generated by $E$ and $F$ if and only if the congruence generated by the union of $E $ and $F$ is equal to the union of the congruences generated by $E $ and $F$, and (2) it is decidable in square time whether the congruence generated by the union of $E$ and $F$ is equal to the union of the congruences generated by $E $ and $F$, where the size of the input is the number of occurrences of symbols in $E$ plus the number of occurrences of symbols in $F$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_14559 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Union of Finitely Generated Congruences on Ground Term Algebra Vágvölgyi, Sándor Symbolic Computation Logic in Computer Science 08A70 We show that for any ground term equation systems $E$ and $F$, (1) the union of the generated congruences by $E$ and $F$ is a congruence on the ground term algebra if and only if there exists a ground term equation system $H$ such that the congruence generated by $H$ is equal to the union of the congruences generated by $E$ and $F$ if and only if the congruence generated by the union of $E $ and $F$ is equal to the union of the congruences generated by $E $ and $F$, and (2) it is decidable in square time whether the congruence generated by the union of $E$ and $F$ is equal to the union of the congruences generated by $E $ and $F$, where the size of the input is the number of occurrences of symbols in $E$ plus the number of occurrences of symbols in $F$. |
| title | Union of Finitely Generated Congruences on Ground Term Algebra |
| topic | Symbolic Computation Logic in Computer Science 08A70 |
| url | https://arxiv.org/abs/2411.14559 |