Name
Title | ||
|---|---|---|
Linear computation of the maximum simultaneous forward and backward bisimulation for node-labeled trees |
Abstract | ||
|---|---|---|
The F&B-index is used to speed up pattern matching in tree and graph data, and is based on the maximum F&B-bisimulation, which can be computed in loglinear time for graphs. It has been shown that the maximum F-bisimulation can be computed in linear time for DAGs. We build on this result, and introduce a linear algorithm for computing the maximum F&B-bisimulation for tree data. It first computes the maximum F-bisimulation, and then refines this to a maximal B-bisimulation. We prove that the result equals the maximum F&B-bisimulation. |
Year | Venue | Keywords |
|---|---|---|
2010 | Xsym | maximal b-bisimulation,tree data,loglinear time,maximum f-bisimulation,linear time,node-labeled tree,graph data,linear computation,linear algorithm,maximum f,pattern matching,indexation |
Field | DocType | Volume |
Graph,Computer science,Linear algorithm,Algorithm,Bisimulation,Log-linear model,Time complexity,Pattern matching,Computation,Speedup | Conference | 6309 |
ISSN | ISBN | Citations |
0302-9743 | 3-642-15683-5 | 1 |
PageRank | References | Authors |
0.36 | 16 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nils Grimsmo | 1 | 25 | 2.80 |
| Truls Amundsen Bjørklund | 2 | 1 | 0.70 |
| Magnus Lie Hetland | 3 | 73 | 8.04 |