Archives of: NUS logic seminar

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.