Search

• < Previous
• 1
• Next >

Separating Regular Languages with First-Order Logic

Given two languages, a separator is a third language that contains the first one and is disjoint from the second one. We investigate the following decision problem: given two regular input languages of finite words, decide whether there exists a first-order definable separator. We prove that in&nbsp;[&hellip;]