Structured Parallel Computation in Structured Documents

Простая страница элемента
dc.creatorSkillicorn,D.
dc.date1997
dc.date.accessioned2024-02-06T12:48:43Z
dc.date.available2024-02-06T12:48:43Z
dc.descriptionDocument archives contain large amounts of data to which sophisticated queries are applied. The size of archives and the complexity of evaluating queries makes the use of parallelism attractive. The use of semantically-based markup such as SGML makes it possible to represent documents and document archives as data types. We present a theory of trees and tree homomorphisms, modelling structured text archives and operations on them, from which it can be seen that: many apparently unrelated tree operations are homomorphisms, homomorphisms can be described in a simple parameterised way that gives standard sequential and parallel implementations for them, and certain special classes of homomorphisms have parallel implementations of practical importance. In particular, we develop an algorithm for path expression search, a novel powerful query facility for structured text, taking time logarithmic in the text size. This algorithm is the first example of a new algorithm discovered using homomorphic skeletons over data types.
dc.formattext/html
dc.identifierhttps://doi.org/10.3217/jucs-003-01-0042
dc.identifierhttps://lib.jucs.org/article/27323/
dc.identifier.urihttps://openrepository.mephi.ru/handle/123456789/7110
dc.languageen
dc.publisherJournal of Universal Computer Science
dc.relationinfo:eu-repo/semantics/altIdentifier/eissn/0948-6968
dc.relationinfo:eu-repo/semantics/altIdentifier/pissn/0948-695X
dc.rightsinfo:eu-repo/semantics/openAccess
dc.rightsJ.UCS License
dc.sourceJUCS - Journal of Universal Computer Science 3(1): 42-68
dc.subjectstructured text
dc.subjectcategorical data type
dc.subjectsoftware development methodology
dc.subjectparallel algorithms
dc.subjectquery evaluation
dc.titleStructured Parallel Computation in Structured Documents
dc.typeResearch Article
Файлы
Коллекции