Name
Abstract | ||
|---|---|---|
Rational patterns are used to specify recognizable tree languages. It is shown that, given a rational patternp and a treet, one can decide inO(¦p¦·¦t¦) steps whether there is some match ofp int. Problems of this kind generalized to forests or nets are shown to be NP-complete. |
Year | DOI | Venue |
|---|---|---|
1983 | 10.1007/BF01257084 | Acta Inf. |
Keywords | Field | DocType |
Information System,Operating System,Data Structure,Communication Network,Information Theory | Information system,Information theory,Discrete mathematics,Data structure,NP-complete,Combinatorics,Formal language,Telecommunications network,Pattern matching,Mathematics | Journal |
Volume | Issue | ISSN |
20 | 3 | 0001-5903 |
Citations | PageRank | References |
0 | 0.34 | 2 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hans-Ulrich Simon | 1 | 567 | 104.52 |
| Mathematik und Informatik der Universit | 2 | 0 | 0.34 |
| SimonHans-Ulrich | 3 | 0 | 0.34 |