Planar Languages and Learnability

摘要: Strings can be mapped into Hilbert spaces using feature maps such as the Parikh map. Languages then defined pre-image of hyperplanes in space, rather than grammars or automata. These are planar languages. In this paper we show that techniques from kernel-based learning, represent and efficiently learn, positive data alone, various linguistically interesting context-sensitive particular cross-serial dependencies Swiss German, established non-context-freeness natural language, learnable a standard kernel. We demonstrate polynomial-time identifiability limit these classes, discuss some language theoretic properties their relationship to choice kernel/feature