title: Identifying hierarchical structure in sequences: a linear-time algorithm

authors: Nevill-Manning, Craig G.

subjects: computer science

abstract: This 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.

text: Identifying hierarchical structure in sequences: a linear-time algorithm This 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.

year: 1996-11

title: A high-resolution full-field range imaging system

authors: Carnegie, Dale A.

subjects: image resolution

abstract: There exist a number of applications where the range to all objects in a field of view needs to be obtained. Specific examples include obstacle avoidance for autonomous mobile robots, process automation in assembly factories, surface profiling for shape analysis, and surveying. Ranging systems can be typically characterized as being either laser scanning systems where a laser point is sequentially scanned over a scene or a full-field acquisition where the range to every point in the image is simultaneously obtained. The former offers advantages in terms of range resolution, while the latter tend to be faster and involve no moving parts. We present a system for determining the range to any object within a camera's field of view, at the speed of a full-field system and the range resolution of some point laser scans. Initial results obtained have a centimeter range resolution for a 10 second acquisition time. Modifications to the existing system are discussed that should provide faster results with submillimeter resolution.

text: A high-resolution full-field range imaging system There exist a number of applications where the range to all objects in a field of view needs to be obtained. Specific examples include obstacle avoidance for autonomous mobile robots, process automation in assembly factories, surface profiling for shape analysis, and surveying. Ranging systems can be typically characterized as being either laser scanning systems where a laser point is sequentially scanned over a scene or a full-field acquisition where the range to every point in the image is simultaneously obtained. The former offers advantages in terms of range resolution, while the latter tend to be faster and involve no moving parts. We present a system for determining the range to any object within a camera's field of view, at the speed of a full-field system and the range resolution of some point laser scans. Initial results obtained have a centimeter range resolution for a 10 second acquisition time. Modifications to the existing system are discussed that should provide faster results with submillimeter resolution.

year: 2005-07

title: Impact of tephra fall and environmental change: a 1000 year record from Matakana Island, Bay of Plenty, North Island, New Zealand.

authors: Giles, Teresa M.

abstract: Palynological evidence was used to determine the development of vegetation communities on Matakana Island, North Island, New Zealand, over the last 1000 radiocarbon years. The pollen record indicates that changes occurred in the vegetation immediately following fallout deposition of the Kaharoa Tephra approximately 100 km from source at c. 665 years BP. Such changes may be a direct response to the impact of tephra fall, although the possibility of anthropogenic disturbance cannot be discounted. As a result of the eruption some taxa (Leucopogon fasciculatus and Tupeia antarctica) became at least temporarily extinct from the area. Two phases of anthropogenic influence on the environment are recorded in the pollen record: Polynesian, followed by European inhabitation of the island, giving a detailed history of human influence in the area for the millennium.

text: Impact of tephra fall and environmental change: a 1000 year record from Matakana Island, Bay of Plenty, North Island, New Zealand. Palynological evidence was used to determine the development of vegetation communities on Matakana Island, North Island, New Zealand, over the last 1000 radiocarbon years. The pollen record indicates that changes occurred in the vegetation immediately following fallout deposition of the Kaharoa Tephra approximately 100 km from source at c. 665 years BP. Such changes may be a direct response to the impact of tephra fall, although the possibility of anthropogenic disturbance cannot be discounted. As a result of the eruption some taxa (Leucopogon fasciculatus and Tupeia antarctica) became at least temporarily extinct from the area. Two phases of anthropogenic influence on the environment are recorded in the pollen record: Polynesian, followed by European inhabitation of the island, giving a detailed history of human influence in the area for the millennium.

year: 1999-01-01