arXiv Open Access 2024

A Uniform Framework for Language Inclusion Problems

Kyveli Doveri Pierre Ganty Chana Weil-Kennedy

Lihat Sumber

Abstrak

We present a uniform approach for solving language inclusion problems. Our approach relies on a least fixpoint characterization and a quasiorder to compare words of the "smaller" language, reducing the inclusion check to a finite number of membership queries in the "larger" language. We present our approach in detail on the case of inclusion of a context-free language given by a grammar into a regular language. We then explore other inclusion problems and discuss how to apply our approach.

Topik & Kata Kunci

cs.FL cs.LO

Penulis (3)

Kyveli Doveri

Pierre Ganty

Chana Weil-Kennedy

Format Sitasi

APA MLA BibTeX

Doveri, K., Ganty, P., Weil-Kennedy, C. (2024). A Uniform Framework for Language Inclusion Problems. https://arxiv.org/abs/2404.09862

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2024
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓