Finitely distinguishable erasing pattern languages with bounded variable frequency
Date/Time :
10 Apr 2019 17:00 Venue : S17 #04-06 SR1 Speaker : Gao Ziyuan,
National University of Singapore
Date/Time:10 Apr 2019 17:00Venue: S17 #04-06 SR1Speaker: Gao Ziyuan, National University of SingaporeFinitely distinguishable erasing pattern languages with bounded variable frequencyA pattern is a nonempty string made up of symbols from two disjoint sets, an alphabet $\Sigma$ of constant symbols and a countably infinite set $X$ of variables. The erasing pattern language $L(\pi)$ generated by a pattern $\pi$ is the set of all words over $\Sigma$ obtained by replacing all the variables of $\pi$ with arbitrary words over $\Sigma$, with the proviso that identical variables be replaced with the same string. In particular, patterns allow for repetitions of variable substrings, a feature known as backreferencing in programming languages. A distinguishing set for any pattern $\pi$ w.r.t. a class $\Pi$ of patterns containing $\pi$ is a set $D$ of words over $\Sigma$ that distinguishes $\pi$ from every other pattern $\tau$ in $\Pi$ with $L(\tau) \neq L(\pi)$ (i.e., $D \cap L(\pi) \neq D \cap L(\tau)$ whenever $L(\tau) \neq L(\pi)$). Two basic types of counting problems will be discussed: first, given any pattern $\pi$ belonging to a class $\Pi$ of patterns, does $\pi$ have a finite distinguishing set w.r.t. $\Pi$; second, what is the minimum size of a distinguishing set for $\pi$ w.r.t. $\Pi$? The latter quantity gives a measure of the information complexity of $\pi$ w.r.t. $\Pi$, and it is known as the (classical) teaching dimension of $\pi$ w.r.t. $\Pi$ in computational learning theory. We also consider the problem of determining, for any given strict partial order $\prec$ on $\Pi$ (up to equivalence of patterns) and any pattern $\pi$ belonging to $\Pi$, the minimum size of a distinguishing set for $\pi$ w.r.t. the subclass of all $\tau$ in $\Pi$ such that $\tau \not\prec \pi$; this quantity is known as the preference-based teaching dimension of $\pi$ w.r.t. $(\Pi,\prec)$. We study how the classical and preference-based teaching dimensions of patterns w.r.t. various “naturally” defined classes of patterns and strict partial orders depend on the alphabet size and the maximum number of variable repetitions in any single pattern belonging to the class.Add to calendar:
