Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102071
Title: Detecting one-variable patterns
Authors: Kosolobov, D.
Manea, F.
Nowotka, D.
Issue Date: 2017
Publisher: Springer Verlag
Citation: Kosolobov D. Detecting one-variable patterns / D. Kosolobov, F. Manea, D. Nowotka. — DOI 10.1007/978-3-319-67428-5_22 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2017. — Vol. 10508 LNCS. — P. 254-270.
Abstract: Given a pattern p = s1x1s2x2 … sr-1xr-1sr such that (Formula presented), where x is a variable and x its reversal, and s1,s2, …, sr are strings that contain no variables, we describe an algorithm that constructs in O(rn) time a compact representation of all P instances of p in an input string of length n over a polynomially bounded integer alphabet, so that one can report those instances in O(P) time. © Springer International Publishing AG 2017.
Keywords: MATCHING
PATTERNS WITH VARIABLES
PSEUDO-REPETITIONS
REPETITIONS
ARTIFICIAL INTELLIGENCE
COMPUTER SCIENCE
COMPUTERS
COMPACT REPRESENTATION
INPUT STRING
INTEGER ALPHABETS
MATCHING
PATTERNS WITH VARIABLES
PSEUDO-REPETITIONS
REPETITIONS
INFORMATION RETRIEVAL
URI: http://hdl.handle.net/10995/102071
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 85030158527
PURE ID: 2121534
6006dbdc-82ca-4493-b5a9-42fb6b9712e4
ISSN: 3029743
ISBN: 9783319674278
DOI: 10.1007/978-3-319-67428-5_22
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-85030158527.pdf649,16 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.