Words-to-Letters Valuations for Language Kleene Algebras with Variable and Constant Complements
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909630803738624 |
|---|---|
| author | Nakamura, Yoshiki Sin'ya, Ryoma |
| author_facet | Nakamura, Yoshiki Sin'ya, Ryoma |
| contents | We investigate the equational theory for Kleene algebra terms with variable complements and constant complements -- (language) complement where it applies only to variables or constants -- w.r.t. languages. While the equational theory w.r.t. languages coincides with the language equivalence (under the standard language valuation) for Kleene algebra terms, this coincidence is broken if we extend the terms with complements. In this paper, we prove the decidability of some fragments of the equational theory: the universality problem is coNP-complete, and the inequational theory $t \le s$ is coNP-complete when $t$ does not contain Kleene-star. To this end, we introduce words-to-letters valuations; they are sufficient valuations for the equational theory and ease us in investigating the equational theory w.r.t. languages. Additionally, we show a completeness theorem of the equational theory for words with variable complements and the non-empty constant. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_16397 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Words-to-Letters Valuations for Language Kleene Algebras with Variable and Constant Complements Nakamura, Yoshiki Sin'ya, Ryoma Logic in Computer Science We investigate the equational theory for Kleene algebra terms with variable complements and constant complements -- (language) complement where it applies only to variables or constants -- w.r.t. languages. While the equational theory w.r.t. languages coincides with the language equivalence (under the standard language valuation) for Kleene algebra terms, this coincidence is broken if we extend the terms with complements. In this paper, we prove the decidability of some fragments of the equational theory: the universality problem is coNP-complete, and the inequational theory $t \le s$ is coNP-complete when $t$ does not contain Kleene-star. To this end, we introduce words-to-letters valuations; they are sufficient valuations for the equational theory and ease us in investigating the equational theory w.r.t. languages. Additionally, we show a completeness theorem of the equational theory for words with variable complements and the non-empty constant. |
| title | Words-to-Letters Valuations for Language Kleene Algebras with Variable and Constant Complements |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2411.16397 |