Remarks about Commutative Context-Free Languages

✍ Scribed by Juha Kortelainen

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 205 KB
• Volume: 56
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1997.1553

✦ Synopsis

We prove that the complement of a commutative language L is context-free if the Parikh-map of L is a proper linear set. Some sharpenings to results considering the Fliess conjecture on commutative contextfree languages are given. A conjecture concerning commutative star languages is disproved by a counterexample.