Det klassiska mönstret som matchar paradigmet är att söka förekomster av en sträng i en annan, där båda strängarna dras från ett alfabet som är inställt i en annan sträng. I den parameteriserade modellen för mönstermatchning är en konsekvent namnändring av symboler från  ska tillåtas i en match. Parameteriserat matchande paradigm har visat sig användbart i problem inom programvaruteknik, datorseende och andra applikationer. I klassisk mönstermatchning är både text och mönster strängar. Program som att söka i xml eller söka i hypertext kräver söksträngar i icke-linjära strukturer såsom träd eller grafer. Det har varit arbete i litteraturen på exakt och ungefärlig parameteriserad matchning, samt arbete på exakt och ungefärlig strängmatchning på icke-linjära strukturer. I detta papper undersöker vi parameteriserad matchning i icke-linjära strukturer. Vi bevisar att exakt parameteriserad matchning på träd kan beräknas i linjär tid för alfabet i en O (n)-storlek heltalsintervall, och med tiden O (n log m) i allmänhet, där n är trädstorlek och m mönstret längd. Dessa gränser är optimala i jämförelsemodellen. Vi visar också att exakt parameteriserad matchning på riktade acykliska grafer (DAG) är N Pfullständig.
Amir och Navarro REF ansåg parameteriserade mönster matchning (PPM ) problem på träd.
Parameterized Matching on Non-linear Structures
{'venue': 'Inf. Process. Lett.', 'journal': 'Inf. Process. Lett.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}