✦ LIBER ✦

Efficient constructions of test sets for regular and context-free languages

✍ Scribed by Juhani Karhuma¨ki; Wojciech Rytter; Stefan Jarominek

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 799 KB
Volume: 116
Category: Article
ISSN: 0304-3975
DOI: 10.1016/0304-3975(93)90325-n

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Polynomial Size Test Sets For Context-Fr

Polynomial Size Test Sets For Context-Free Languages

✍ J. Karhumaki; W. Plandowski; W. Rytter 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 648 KB

We prove that each context-free language possesses a test set of size \(O\left(m^{6}\right)\), where \(m\) is the number of productions in a grammar-producing the language. A context-free grammar generating the test set can be found in polynomial time by a sequential algorithm. It improves the doubl

A graph-based regularity test for determ

A graph-based regularity test for deterministic context-free languages

✍ Priti Shankar; B.S. Adiga 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 550 KB