On inferring linear single-tree languages

Authors
Makinen, E
Citation
E. Makinen, On inferring linear single-tree languages, INF PROCESS, 73(1-2), 2000, pp. 1-3
Citations number
6
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION PROCESSING LETTERS
ISSN journal
00200190 → ACNP
Volume
73
Issue
1-2
Year of publication
2000
Pages
1 - 3
Database
ISI
SICI code
0020-0190(20000131)73:1-2<1:OILSL>2.0.ZU;2-E
Abstract
We consider the inferability of linear single-tree languages. We are able t o show that if the terminal productions of the corresponding grammars obey a simple restriction, then the languages generated are inferable from posit ive samples only. Moreover, we solve an open problem posed by Greibach, Shi , and Simonson concerning the unambiguity of certain ultralinear single-tre e grammars. (C) 2000 Elsevier Science B.V. All rights reserved.