Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 11 October 2017, 17:00 hrs

Room: S17#04-04, Department of Mathematics, NUS

Speaker: Gao Ziyuan

Title: Erasing pattern languages distinguishable by a finite number of strings

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Abstract:

Pattern languages have been an object of study in various subfields of

computer science for decades. We introduce and study a decision

problem on patterns called the finite distinguishability problem:

given a pattern pi, are there finite sets T+ and T- of

strings such that the only pattern language containing all strings in

T+ and none of the strings in T- is the language generated by

pi? This problem is related to the complexity of teacher-directed

learning, as studied in computational learning theory, as well as to

the long-standing open question whether the equivalence of two

patterns is decidable. We show that finite distinguishability is

decidable if the underlying alphabet is of size other than 2 or 3, and

provide a number of related results, such as (i) partial solutions for

alphabet sizes 2 and 3, and (ii) decidability proofs for variants of

the problem for special subclasses of patterns, namely, regular,

1-variable, and non-cross patterns. For the same subclasses, we

further determine the values of two complexity parameters in

teacher-directed learning, namely the teaching dimension and the

recursive teaching dimension.