TY - GEN
T1 - Learning left-to-right and right-to-left iterative languages
AU - Heinz, Jeffrey
PY - 2008
Y1 - 2008
N2 - The left-to-right and right-to-left iterative languages are previously unnoticed subclasses of the regular languages of infinite size that are identifiable in the limit from positive data. Essentially, these language classes are the ones obtained by merging final states in a prefix tree and initial states in a suffix tree of the observed sample, respectively. Strikingly, these classes are also transparently related to the zero-reversible languages because some algorithms that learn them differ minimally from the ZR algorithm given in Angluin (1982). Second, they are part of the answer to the challenge provided by Muggleton (1990), who proposed mapping the space of language classes obtainable by a general state-merging algorithm IM1. Third, these classes are relevant to a hypothesis of how children can acquire sound patterns of their language-in particular, the hypothesis that all phonotactic patterns found in natural language are neighborhood-distinct (Heinz 2007).
AB - The left-to-right and right-to-left iterative languages are previously unnoticed subclasses of the regular languages of infinite size that are identifiable in the limit from positive data. Essentially, these language classes are the ones obtained by merging final states in a prefix tree and initial states in a suffix tree of the observed sample, respectively. Strikingly, these classes are also transparently related to the zero-reversible languages because some algorithms that learn them differ minimally from the ZR algorithm given in Angluin (1982). Second, they are part of the answer to the challenge provided by Muggleton (1990), who proposed mapping the space of language classes obtainable by a general state-merging algorithm IM1. Third, these classes are relevant to a hypothesis of how children can acquire sound patterns of their language-in particular, the hypothesis that all phonotactic patterns found in natural language are neighborhood-distinct (Heinz 2007).
UR - https://www.scopus.com/pages/publications/56649088041
U2 - 10.1007/978-3-540-88009-7_7
DO - 10.1007/978-3-540-88009-7_7
M3 - Conference contribution
AN - SCOPUS:56649088041
SN - 3540880089
SN - 9783540880080
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 84
EP - 97
BT - Grammatical Inference
T2 - 9th International Colloquium on Grammatical Inference, ICGI 2008
Y2 - 22 September 2008 through 24 September 2008
ER -