arXiv Open Access 2018

On shuffle products, acyclic automata and piecewise-testable languages

Simon Halfon Philippe Schnoebelen

Lihat Sumber

Abstrak

We show that the shuffle $L \unicode{x29E2} F$ of a piecewise-testable language $L$ and a finite language $F$ is piecewise-testable. The proof relies on a classic but little-used automata-theoretic characterization of piecewise-testable languages. We also discuss some mild generalizations of the main result, and provide bounds on the piecewise complexity of $L \unicode{x29E2} F$.

Topik & Kata Kunci

cs.FL

Penulis (2)

Simon Halfon

Philippe Schnoebelen

Format Sitasi

APA MLA BibTeX

Halfon, S., Schnoebelen, P. (2018). On shuffle products, acyclic automata and piecewise-testable languages. https://arxiv.org/abs/1810.02953

Akses Cepat

Lihat di Sumber

Informasi Jurnal

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