Metraipolis › archive › dc_b570c36cd755

An Analysis of Decision Problems for Relational Pattern Languages under Various Constraints — arXiv:2610.07119

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.07119
License (as archived)
CC0-1.0
Archived
2026-10-07T15:02:05.605Z
SHA-256 of the archived text
67ee961f3fcbf68b8251bb17c3f11ddd032ce3a66a6e24eb1898379fbd679eab
Stable URL of this page
https://metraipolis.com/documento/dc_b570c36cd755

How to cite

An Analysis of Decision Problems for Relational Pattern Languages under Various Constraints — arXiv:2610.07119 — arXiv (en), https://arxiv.org/abs/2610.07119 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b570c36cd755 (Metraipolis archive dc_b570c36cd755, sha256 67ee961f3fcbf68b8251bb17c3f11ddd032ce3a66a6e24eb1898379fbd679eab)
BibTeX
@misc{dcb570c36cd755,
  title = {An Analysis of Decision Problems for Relational Pattern Languages under Various Constraints — arXiv:2610.07119},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.07119},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b570c36cd755; sha256 67ee961f3fcbf68b8251bb17c3f11ddd032ce3a66a6e24eb1898379fbd679eab},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.07119. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Patterns are words with terminals and variables. The language of a pattern is the set of words obtained by uniformly substituting all variables with words that contain only terminals. In their original definition, patterns only allow for multiple distinct occurrences of some variables to be related by the equality relation, represented by using the same variable multiple times. In an extended notion, called relational patterns and relational pattern languages, variables may be related by arbitrary other relations, achieved by using regular patterns and relating individual variables independently from the patterns structure separately. We extend the ongoing investigation of the main decision problems for patterns (namely, the equivalence problem, the inclusion problem, and the membership problem) to relational pattern languages under a wide range of relevant individual relations, providing a comprehensive foundation in all three research directions.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Formal Languages and Automata Theory (cs.FL) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2610.07119 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T14:35:13.549Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).