A note on parsing pattern languages

Oscar H. Ibarra; Ting Chuen Pong; Stephen M. Sohn

doi:10.1016/0167-8655(94)00091-G

A note on parsing pattern languages

Oscar H. Ibarra
, Ting Chuen Pong^*
, Stephen M. Sohn

^*Corresponding author for this work

Department of Computer Science and Engineering

Research output: Contribution to journal › Journal Article › peer-review

15 Citations (Scopus)

Abstract

We give an algorithm for parsing pattern languages. We show that a string of length n can be parsed with respect to a k-variable pattern in O(n^k) time using O(n) space. Moreover, the time bound can be reduced by accounting for the number of occurrences of variables in the pattern. We also present evidence that employing some results of elementary number theory and integer linear programming leads to a faster algorithm.

Original language	English
Pages (from-to)	179-182
Number of pages	4
Journal	Pattern Recognition Letters
Volume	16
Issue number	2
DOIs	https://doi.org/10.1016/0167-8655(94)00091-G
Publication status	Published - Feb 1995

Access to Document

10.1016/0167-8655(94)00091-G

Cite this

@article{c97a122acd40429faf30b104127854db,

title = "A note on parsing pattern languages",

abstract = "We give an algorithm for parsing pattern languages. We show that a string of length n can be parsed with respect to a k-variable pattern in O(nk) time using O(n) space. Moreover, the time bound can be reduced by accounting for the number of occurrences of variables in the pattern. We also present evidence that employing some results of elementary number theory and integer linear programming leads to a faster algorithm.",

author = "Ibarra, \{Oscar H.\} and Pong, \{Ting Chuen\} and Sohn, \{Stephen M.\}",

year = "1995",

month = feb,

doi = "10.1016/0167-8655(94)00091-G",

language = "English",

volume = "16",

pages = "179--182",

journal = "Pattern Recognition Letters",

issn = "0167-8655",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - A note on parsing pattern languages

AU - Ibarra, Oscar H.

AU - Pong, Ting Chuen

AU - Sohn, Stephen M.

PY - 1995/2

Y1 - 1995/2

N2 - We give an algorithm for parsing pattern languages. We show that a string of length n can be parsed with respect to a k-variable pattern in O(nk) time using O(n) space. Moreover, the time bound can be reduced by accounting for the number of occurrences of variables in the pattern. We also present evidence that employing some results of elementary number theory and integer linear programming leads to a faster algorithm.

AB - We give an algorithm for parsing pattern languages. We show that a string of length n can be parsed with respect to a k-variable pattern in O(nk) time using O(n) space. Moreover, the time bound can be reduced by accounting for the number of occurrences of variables in the pattern. We also present evidence that employing some results of elementary number theory and integer linear programming leads to a faster algorithm.

UR - https://www.webofscience.com/wos/woscc/full-record/WOS:A1995QH31300007

UR - https://openalex.org/W2067656180

U2 - 10.1016/0167-8655(94)00091-G

DO - 10.1016/0167-8655(94)00091-G

M3 - Journal Article

SN - 0167-8655

VL - 16

SP - 179

EP - 182

JO - Pattern Recognition Letters

JF - Pattern Recognition Letters

IS - 2

ER -

A note on parsing pattern languages

Abstract

Access to Document

Other files and links

Fingerprint

Cite this