Testing Simon’s congruence

Piecewise testable languages are a subclass of the regular languages. There are many equivalent ways of defining them; Simon’s congruence ∼kis one of the most classical approaches. Two words are ∼k-equivalent if they have the same set of (scattered) subwords of length at most k. A language L is piec...

Full description

Saved in:
Bibliographic Details
Main Authors: Lukas Fleischer, Manfred Kufleitner
Format: Default Conference proceeding
Published: 2018
Subjects:
Other information and computing sciences not elsewhere classified
Regular language
Scattered subword
Piecewise testability
String algorithm
Information and Computing Sciences not elsewhere classified
Online Access:https://hdl.handle.net/2134/36029
Tags: Add Tag
No Tags, Be the first to tag this record!

Similar Items