Search

• < Previous
• 1
• Next >

The height of piecewise-testable languages and the complexity of the logic of subwords

The height of a piecewise-testable language $L$ is the maximum length of the words needed to define $L$ by excluding and requiring given subwords. The height of $L$ is an important descriptive complexity measure that has not yet been investigated in a systematic way. This article develops a series&nbsp;[&hellip;]