Show simple item record  

dc.contributor.authorNevill-Manning, Craig G.
dc.contributor.authorWitten, Ian H.
dc.date.accessioned2008-10-29T02:54:24Z
dc.date.available2008-10-29T02:54:24Z
dc.date.issued1996-11
dc.identifier.citationNevill-Manning, C. G. & Witten, I. H. (1996). Authorship patterns in information systems. (Working paper 96/25). Hamilton, New Zealand: University of Waikato, Department of Computer Science.en_US
dc.identifier.issn1170-487X
dc.identifier.urihttps://hdl.handle.net/10289/1186
dc.description.abstractThis paper describes an algorithm that infers a hierarchical structure from a sequence of discrete symbols by replacing phrases which appear more than once by a grammatical rule that generates the phrase, and continuing this process recursively. The result is a hierarchical representation of the original sequence. The algorithm works by maintaining two constraints: every diagram in the grammar must be unique, and every rule must be used more than once. It breaks new ground by operating incrementally. Moreover, its simple structure permits a proof that it operates in space and time that is linear in the size of the input. Our implementation can process 10,000 symbols/second and has been applied to an extensive range of sequences encountered in practice.en_US
dc.format.mimetypeapplication/pdf
dc.language.isoen
dc.relation.ispartofseriesComputer Science Working Papers
dc.subjectcomputer scienceen_US
dc.subjectsequence learningen_US
dc.subjectgrammatical inferenceen_US
dc.subjectlinear-time learning algorithmsen_US
dc.subjectMachine learning
dc.titleIdentifying hierarchical structure in sequences: a linear-time algorithmen_US
dc.typeWorking Paperen_US
dc.identifier.doi10.1613/jair.374en_NZ
uow.relation.series96/25
dc.relation.isPartOfJournal of Artificial Intelligence Researchen_NZ
pubs.begin-page67en_NZ
pubs.elements-id39440
pubs.end-page82en_NZ
pubs.issue7en_NZ
pubs.volume.en_NZ


Files in this item

This item appears in the following Collection(s)

Show simple item record