Fast Pattern Matching in Strings
From MaRDI portal
Publication:4148937
DOI10.1137/0206024zbMath0372.68005OpenAlexW1985108724WikidataQ55881317 ScholiaQ55881317MaRDI QIDQ4148937
James H. Jun. Morris, Donald E. Knuth, Vaughan R. Pratt
Publication date: 1977
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/44799559a1067e06b5a6bf052f8f10637707928f
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Formal languages and automata (68Q45) General topics in the theory of software (68N01) Algorithms in computer science (68W99)
Related Items
Optimal algorithms for finding the symmetries of a planar point set, Structural properties of the string statistics problem, Efficient string matching with k mismatches, An optimal algorithm to compute all the covers of a string, Dynamic dictionary matching with failure functions, On two-dimensional pattern-matching languages and their decision problems, Le calcul rapide des mélanges de deux mots. (Fast computing of the shuffle of two words), A greedy approximation algorithm for constructing shortest common superstrings, On the connectivity of the De Bruijn graph, Complexity, combinatorial group theory and the language of palutators, Remarks on string-matching and one-way multihead automata, Fast string matching with k differences, Parallel processing of encoded bit strings, Matching patterns in strings subject to multi-linear transformations, La reconnaissance des facteurs d'un langage fini dans un texte en temps linéaire. (Recognition of the factors of a finite language in a text in linear time), On the subtree isomorphism problem for ordered trees, On some properties of very pure codes, A string searching algorithm, Lexicographically least circular substrings, Linear-time string-matching using only a fixed number of local storage locations, Fast string searching by finding subkeys in subtext, Finding patterns common to a set of strings, String overlaps, pattern matching, and nontransitive games, Periods in strings, An optimal algorithm for computing the repetitions in a word, String matching with weighted errors, A combinatorial property of the Fibonacci words, An analysis of the Karp-Rabin string matching algorithm, A linear-time algorithm for finding approximate shortest common superstrings, Do-it-yourself type theory, A fast pattern matching algorithm derived by transformational and assertional reasoning, Parallel construction of minimal suffix and factor automata, Relationship between the period of a finite word and the length of its unbordered segments, Decision problems for finite special string-rewriting systems that are confluent on some congruence class, On some combinatorial problems in free monoids, Searching for a set of correlated patterns, A simple fast hybrid pattern-matching algorithm, Steady-paced-output and fractional-on-line algorithms on a RAM, Optimal off-line detection of repetitions in a string, Property matching and weighted matching, Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays, Multiple pattern matching: a Markov chain approach, Optimal canonization of all substrings of a string, Correctness and efficiency of pattern matching algorithms, Average running time of the Boyer-Moore-Horspool algorithm, String-matching on ordered alphabets, Two recognizable string-matching problems over free partially commutative monoids, Optimal algorithms for computing the canonical form of a circular string, A variation on the Boyer-Moore algorithm, A string-matching interpretation of the equation \(x^ m y^ n = z^ p\), Fast average-case pattern matching by multiplexing sparse tables, An efficient algorithm for the all pairs suffix-prefix problem, A practical method for implementing string pattern matching machines, Partial memoization for obtaining linear time behavior of a 2DPDA, Fast pattern-matching on indeterminate strings, Efficient on-line repetition detection, Fast detection and display of symmetry in outerplanar graphs, Finding all the palindromes in a binary tree in linear time and space, Efficient algorithms for the block edit problems, String matching problems over free partially commutative monoids, Efficient CRCW-PRAM algorithms for universal substring searching, Identifying periodic occurrences of a template with applications to protein structure, Two-dimensional dictionary matching, An on-line string superprimitivity test, Deciding whether a finite set of words has rank at most two, Optimal prefix and suffix queries on texts, A new taxonomy of sublinear right-to-left scanning keyword pattern matching algorithms, An application of pattern matching to a problem in geometrical complexity, Parameterized matching on non-linear structures, An O(N) algorithm for finding periodicity of a sequence using hash coding, An improved algorithm to check for polygon similarity, Palindrome recognition in real time by a multitape Turing machine, Faster pattern matching with character classes using prime number encoding, A fast equivalence-checking algorithm for circular lists, Periodes et repetitions des mots du monoide libre, Burrows-Wheeler transform and Sturmian words, On polygon similarity, Waiting time and complexity for matching patterns with automata, Shift-or string matching with super-alphabets, Disjunctive partial deduction of a right-to-left string-matching algorithm, Fast parameterized matching with \(q\)-grams, Optimal parallel two dimensional text searching on a CREW PRAM, Real two dimensional scaled matching, The factors analysis and algorithm implementation of single-pattern matching, Intertwinings of periodic sequences, Searching for gapped palindromes, Transforming curves on surfaces, Detecting palindromes, patterns and borders in regular languages, Everywhere \(\alpha \)-repetitive sequences and Sturmian words, Constant-space string-matching in sublinear average time, Quasiperiodicity and string covering, On the Ehrenfeucht-Mycielski sequence, Average-optimal string matching, Two-dimensional pattern matching by two-dimensional on-line tessellation acceptors, A linear time solution to the single function coarsest partition problem, The smallest automaton recognizing the subwords of a text, The derivation of on-line algorithms, with an application to finding palindromes, Three one-way heads cannot do string matching, Alphabet dependence in parameterized matching, New algorithms for the LCS problem, Average-case complexity of the Whitehead problem for free groups, A Heuristic For Computing Repeats With A Factor Oracle: Application To Biological Sequences, New and faster filters for multiple approximate string matching, PAMA: A FAST STRING MATCHING ALGORITHM, Pattern matching in trace monoids, A Chaotic Image Encryption Scheme Based on Genetic Central Dogma and KMP Method, Efficient preprocessing of simple binary pattern forests, Classes of equational programs that compile into efficient machine code, Fast algorithms for two dimensional and multiple pattern matching, Boyer-Moore approach to approximate string matching, Improved length bounds for the shortest superstring problem, On-Line Approximate String Searching Algorithms: Survey and Experimental Results, An 0(1) time algorithm for string matching, Demonic operators and monotype factors, EFFICIENT PARALLEL ALGORITHMS FOR PATTERN RECOGNITION∗, A concurrent multi-string matching from multi-text algorithm based on the algorithm of Hamiltonian Path Problem and DNA computation, A Bit-Parallel Exact String Matching Algorithm for Small Alphabet, The Burrows-Wheeler Transform between Data Compression and Combinatorics on Words, On linear-time alphabet-independent 2-dimensional pattern matching, Pattern matching in hypertext, New characterizations of exponential, elementary, and non-elementary time-bounded Turing machines, Relativized adjacency, Bit catastrophes for the Burrows-Wheeler transform, On the Complexity of String Matching for Graphs, Inferring strings from position heaps in linear time, Unnamed Item, String attractors and infinite words, String rearrangement inequalities and a total order between primitive words, Confluence of one-rule Thue systems, SQUARE COMPLETION OPERATION OF MAXIMAL SUFFIX IN FIBONACCI WORD, Ranking and unranking bordered and unbordered words, Характеризация чисел Фибоначчи, Lowerbounds for Bisimulation by Partition Refinement, String Covering: A Survey, Quantum string matching unfolded and extended, Quantum algorithm for lexicographically minimal string rotation, Unnamed Item, Unnamed Item, Sequentially swapping tokens: further on graph classes, Unnamed Item, Unnamed Item, A positive supercompiler, Efficient string matching on packed texts, A fast average case algorithm for lyndon decomposition, Detecting the morphic images of a word : improving the general algorithm, Palindromic Decompositions with Gaps and Errors, Linear and Efficient String Matching Algorithms Based on Weak Factor Recognition, Optimal parallel algorithms for Prefix Matching, Optimal two-dimensional compressed matching, String Matching: Communication, Circuits, and Learning., Counting Palindromes in Substrings, AN IMPROVED PREFIX-FREE REGULAR-EXPRESSION MATCHING, Efficient multi-attribute pattern matching, THEORETICAL ISSUES OF SEARCHING AERIAL PHOTOGRAPHS: A BIRD'S EYE VIEW, A FRAMEWORK FOR THE DYNAMIC IMPLEMENTATION OF FINITE AUTOMATA FOR PERFORMANCE ENHANCEMENT, A high-speed dynamic full-text search method by using memory management, Unnamed Item, Real-time recognition of substring repetition and reversal, IDENTIFYING ALL ABELIAN PERIODS OF A STRING IN QUADRATIC TIME AND RELEVANT PROBLEMS, Computation of Maximal Determinants of Binary Circulant Matrices, One-unambiguous regular languages, One-unambiguous regular languages, Low complexity algorithms in knot theory, A fast and compact technique of implementing transition tables for finite state automata, Unnamed Item, Periodicity in data streams with wildcards, An algorithm for deciding if a polyomino tiles the plane, Unnamed Item, Unnamed Item, Unnamed Item, Minimal forbidden factors of circular words, Efficient Protocols for Set Intersection and Pattern Matching with Security Against Malicious and Covert Adversaries, Window-accumulated subsequence matching problem is linear, Maximal unbordered factors of random strings, Approximate periods of strings, Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries, Indexing Circular Patterns, Optimal parallel algorithms for periods, palindromes and squares, The simultaneous conjugacy problem in the symmetric group, Creating improvisations on chord progressions using suffix trees, On computational complexity of set automata, Unnamed Item, THE DESIGN PRINCIPLES AND ALGORITHMS OF A WEIGHTED GRAMMAR LIBRARY, A New String Matching Algorithm, A sublinear time string prefix square detection algorithm, Cartesian Tree Matching and Indexing, Quasi-Periodicity in Streams, Speeding up two string-matching algorithms, The complete-tree-like matching mc-DFA and their implementation, A note on mc-DFA and its minimization, Unnamed Item, MULTIPSEUDOPERIODIC WORDS, A note on special thue systems with a single defining relation, Unnamed Item, Linear time algorithm for the conjugacy problem in the first Grigorchuk group, Parallel String Matching, Proof-directed program transformation: A functional account of efficient regular expression matching, Elastic-Degenerate String Matching via Fast Matrix Multiplication, Faster Online Elastic Degenerate String Matching, Transcendence of Sturmian or morphic continued fractions, Collage system: A unifying framework for compressed pattern matching., A new regular grammar pattern matching algorithm., On maximal suffixes and constant-space linear-time versions of KMP algorithm., Bounded degree graph inference from walks, Faster implementation of a shortest superstring approximation, Speeding up two string-matching algorithms, On Boyer-Moore automata, Sublinear approximate string matching and biological applications, A sublinear algorithm for approximate keyword searching, Dynamic dictionary matching, Refined simulation of multihead automata, Average complexity of exact and approximate multiple string matching, The Range Automaton: an efficient approach to text-searching, Squares, cubes, and time-space efficient string searching, Some combinatorial properties of Sturmian words, A polynomial algorithm for deciding bisimilarity of normed context-free processes, Grammar index by induced suffix sorting, On the language of primitive words, Efficient matching of nonrectangular shapes., On the look-ahead problem in lexical analysis, Detecting morphic images of a word: On the rank of a pattern, Finding all periods and initial palindromes of a string in parallel, Multiple filtration and approximate pattern matching, A subquadratic algorithm for approximate limited expression matching, Saving comparisons in the Crochemore-Perrin string-matching algorithm, Fibonacci numbers and words, The zooming method: A recursive approach to time-space efficient string-matching, A filtering algorithm for \(k\)-mismatch with don't cares, Covering a string, EERTREE: an efficient data structure for processing palindromes in strings, Validating the Knuth-Morris-Pratt failure function, fast and online, Parameterized complexity of superstring problems, The generalized definitions of the two-dimensional largest common substructure problems, A characterization of the squares in a Fibonacci string, Undecidable properties of monoids with word problem solvable in linear time., Inplace run-length 2d compressed search., Periodicity, morphisms, and matrices., Overlap matching., On building cyclic and shared structures in Haskell, The indexing for one-dimensional proportionally-scaled strings, Inverse star, borders, and palstars, Efficient online string matching based on characters distance text sampling, Finding patterns and periods in Cartesian tree matching, Dictionary matching with a bounded gap in pattern or in text, Fast algorithms for single and multiple pattern Cartesian tree matching, A combinatorial view on string attractors, Experimental evaluation of algorithms for computing quasiperiods, Optimal pattern matching algorithms, An algorithm to compute the character access count distribution for pattern matching algorithms, A simple algorithm for solving for the generalized longest common subsequence (LCS) problem with a substring exclusion constraint, A faster quick search algorithm, On string matching with mismatches, Wrapper induction: Efficiency and expressiveness, On-line weighted pattern matching, Finding maximal 2-dimensional palindromes, Streaming pattern matching with \(d\) wildcards, On the string matching with \(k\) mismatches, Verifiable pattern matching on outsourced texts, A randomized numerical aligner (rNA), Permuted pattern matching algorithms on multi-track strings, Computing regularities in strings: a survey, The wide window string matching algorithm, Partial words and the critical factorization theorem, A parameterized multilevel pattern matching architecture on FPGAs for network intrusion detection and prevention, Efficient construction of maximal and minimal representations of motifs of a string, Fast parallel and serial multidimensional approximate array matching, Improved pattern-scan-order algorithms for string matching, An efficient generalized shift-rule for the prefer-max de Bruijn sequence, On algorithms that effectively distinguish gradient-like dynamics on surfaces, Complexity of substring search in a set of strings, Succinct non-overlapping indexing, Inverse Lyndon words and inverse Lyndon factorizations of words, Efficient and secure outsourced approximate pattern matching protocol, Efficient pattern matching in elastic-degenerate strings, Accelerated partial decoding in wavelet trees, The order-preserving pattern matching problem in practice, A brief history of parameterized matching problems, Fast string matching for DNA sequences, An improvement of the Aho-Corasick machine, Transducers and repetitions, Optimal algorithms for symmetry detection in two and three dimensions, Top tree compression of tries, Detecting leftmost maximal periodicities, Tight tradeoffs for real-time approximation of longest palindromes in streams, An efficient null-free procedure for deciding regular language membership, Detection of periodicities and string-matching in real time, Time-space-optimal string matching, Sliding suffix tree, Normal forms of quasiperiodic strings, Quantum algorithms for string processing, Fast and practical approximate string matching, Approximate swapped matching., Correctness of substring-preprocessing in Boyer-Moore's pattern matching algorithm, Order-preserving pattern matching indeterminate strings, Finding approximate palindromes in strings, Quantum algorithm for learning secret strings and its experimental demonstration, Application of max-plus algebra to biological sequence comparisons, Efficient string matching based on a two-step simulation of the suffix automaton, Computing the maximum exponent in a stream, Subsequence automata with default transitions, On-line string matching in highly similar DNA sequences, On representations of ternary order relations in numeric strings, Engineering a lightweight external memory suffix array construction algorithm, Faster average case low memory semi-external construction of the Burrows-Wheeler transform, An Efficient Protocol for Oblivious DFA Evaluation and Applications, Computing q-Gram Non-overlapping Frequencies on SLP Compressed Texts, Prefix-Suffix Square Completion, Factor theory and the unity of opposites, Dictionary Matching in a Stream, On left and right seeds of a string, Computing equality-free and repetitive string factorisations, Maximally-Polyvariant Partial Evaluation in Polynomial Time, String matching with simple devices, ADAPTING BOYER-MOORE-LIKE ALGORITHMS FOR SEARCHING HUFFMAN ENCODED TEXTS, ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS, An aperiodicity problem for multiwords, Efficient solution of some problems in free partially commutative monoids, Remarks on Privileged Words, A Fast Suffix Automata Based Algorithm for Exact Online String Matching, Space-Efficient Frameworks for Top- k String Retrieval, Amortized Computational Complexity, A note on thue systems with a single defining relation, Succinct 2D dictionary matching, Computing Equality-Free String Factorisations, Palindromic decompositions with gaps and errors, In-place algorithms for exact and approximate shortest unique substring problems, Pseudoknot-generating operation, Secure parameterized pattern matching, Weighted approximate parameterized string matching, Components and acyclicity of graphs. An exercise in combining precision with concision, Succinct Non-overlapping Indexing, Dictionary Matching with Uneven Gaps, A Characterization of NP Within Interval-Valued Computing, Run-Length Encoded Nondeterministic KMP and Suffix Automata, Can we recover the cover?, A weak approach to suffix automata simulation for exact and approximate string matching, Unnamed Item, Order-preserving pattern matching with scaling, Accelerating Boyer Moore Searches on Binary Texts, On the relationship between histogram indexing and block-mass indexing, Indexing a sequence for mapping reads with a single mismatch, Improved characters distance sampling for online and offline text searching, Searching for Gapped Palindromes, Accretive computation of global transformations, Towards optimal packed string matching, Approximating the maximum consecutive subsums of a sequence, Compact suffix automata representations for searching long patterns, Double string tandem repeats, Average-case linear-time similar substring searching by the \(q\)-gram distance, Simple and efficient LZW-compressed multiple pattern matching, A dynamic programming solution to a generalized LCS problem, An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints, A hierarchy for circular codes, Friends with Benefits, Finite Automata, Palindromes, Powers, and Patterns, On-line string matching algorithms: survey and experimental results, Partial words and the critical factorization theorem revisited, Efficient one-dimensional real scaled matching, Worst Case Efficient Single and Multiple String Matching in the RAM Model, A method for improving full text search using signature files, Parallel String Matching Algorithms, String-Matching and Alignment Algorithms for Finding Motifs in NGS Data, Prefix-free regular languages and pattern matching, Generalized function matching, Succincter Text Indexing with Wildcards, Real-Time Streaming String-Matching, Simple Real-Time Constant-Space String Matching, Faster Subsequence and Don’t-Care Pattern Matching on Compressed Texts, Efficient and Secure Generalized Pattern Matching via Fast Fourier Transform, An artificial neural network based approach for online string matching/filtering of large databases, Fast string matching for multiple searches, Some perils of performance prediction: a case study on pattern matching, PATTERN MATCHING CODE MINIMIZATION IN REWRITING-BASED PROGRAMMING LANGUAGES, WORDS GUARANTEEING MINIMUM IMAGE, Unnamed Item, NR‐grep: a fast and flexible pattern‐matching tool, Fast String Matching in Stationary Ergodic Sources, Extensions to the kronecker-weierstrass theory of pencils, Towards Decidability of Conjugacy of Pairs and Triples, Fast string matching by using probabilities: on an optimal mismatch variant of Horspool's algorithm, On the Key Dependent Message Security of the Fujisaki-Okamoto Constructions, Unnamed Item, Self-overlapping Occurrences and Knuth-Morris-Pratt Algorithm for Weighted Matching, Efficient validation and construction of border arrays and validation of string matching automata, Fast Searching in Packed Strings, Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard, The foundations of the logic ofN-tuples, Verifiable Pattern Matching on Outsourced Texts, The conjugacy problem in subgroups of right-angled Artin groups, A Very Fast String Matching Algorithm Based on Condensed Alphabets, Efficient Algorithms for the Order Preserving Pattern Matching Problem, A Practical Simulation Result for Two-Way Pushdown Automata, EFFICIENT VARIANTS OF THE BACKWARD-ORACLE-MATCHING ALGORITHM, AN ADAPTIVE HYBRID PATTERN-MATCHING ALGORITHM ON INDETERMINATE STRINGS, INFERRING STRINGS FROM COVER ARRAYS, Constrained tree inclusion, A SPACE EFFICIENT BIT-PARALLEL ALGORITHM FOR THE MULTIPLE STRING MATCHING PROBLEM, DYNAMIC ALLOCATION OF FINITE AUTOMATA STATES FOR FAST STRING RECOGNITION, Distributive ρ-calculus, Near-optimal quantum algorithms for string problems, String matching algorithms and automata, Sparse suffix trees, Quantum algorithms for learning hidden strings with applications to matroid problems, Two-way machines and de Bruijn words, Approximate string matching using compressed suffix arrays, Tight bounds on the complexity of the Apostolico-Giancarlo algorithm, Document retrieval with one wildcard, Novel results on the number of runs of the Burrows-Wheeler-transform, Automata evaluation and text search protocols with simulation-based security, K-M-P string matching revisited, Efficient special cases of pattern matching with swaps, Scaled and permuted string matching, A coarse-grained multicomputer algorithm for the detection of repetitions, Resource scheduling with variable requirements over time, Set intersection and sequence matching with mismatch counting, Permuted scaled matching, Light-based string matching, A fast algorithm for finding the positions of all squares in a run-length encoded string, Compression of finite-state automata through failure transitions, Accelerating Boyer-Moore searches on binary texts, An optimizing compiler for parallel chemistry simulations, Construction of Aho Corasick automaton in linear time for integer alphabets, Multiple serial episodes matching, On obtaining the Boyer-Moore string-matching algorithm by partial evaluation, Closed factorization, Pattern matching with don't cares and few errors, Periodicity in rectangular arrays, On pattern matching with \(k\) mismatches and few don't cares, String-matching with OBDDs, The origins of combinatorics on words, The submatrices character count problem: An efficient solution using separable values, Compact and tractable automaton-based representations of time granularities, A unifying look at the Apostolico--Giancarlo string-matching algorithm, Some string matching problems from bioinformatics which still need better solutions, Practical and flexible pattern matching over Ziv-Lempel compressed text., String matching and 1d lattice gases, A series of algorithmic results related to the iterated hairpin completion, Distinct squares in run-length encoded strings, A new filtration method and a hybrid strategy for approximate string matching, Simple real-time constant-space string matching, Compressed indexes for text with wildcards, Enhanced string covering, Algorithms for path-constrained sequence alignment, Efficient index for retrieving top-\(k\) most frequent documents, Counting the palstars, Fast and flexible packed string matching, A filtration method for order-preserving matching, On the bit-parallel simulation of the nondeterministic Aho-Corasick and suffix automata for a set of patterns, String matching with alphabet sampling, A new efficient indexing algorithm for one-dimensional real scaled patterns, Negative selection algorithms on strings with efficient training and linear-time classification, A compact representation of nondeterministic (suffix) automata for the bit-parallel approach, Efficient retrieval of approximate palindromes in a run-length encoded string, Average complexity of backward \(q\)-gram string matching algorithms, Efficient algorithms for local ranking, String matching with variable length gaps, Worst-case efficient single and multiple string matching on packed texts in the word-RAM model, Verifying and enumerating parameterized border arrays, An algorithmic toolbox for periodic partial words, Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion, How the character comparison order shapes the shift function of on-line pattern matching algorithms, A fast algorithm for string matching with mismatches, Multiple matching of parameterized patterns, Parallel detection of all palindromes in a string, Fast parallel string prefix-matching, A generic framework for symbolic execution: a coinductive approach, Algorithms for jumbled indexing, jumbled border and jumbled square on run-length encoded strings, Linear-time computation of prefix table for weighted strings {\&} applications, Two fast constructions of compact representations of binary words with given set of periods, Generalized pattern matching and periodicity under substring consistent equivalence relations, Efficient computation of maximal anti-exponent in palindrome-free strings, Designing optimal- and fast-on-average pattern matching algorithms, Quantum pattern matching fast on average, A grouping approach for succinct dynamic dictionary matching, A sheaf-theoretic approach to pattern matching and related problems, On Simon's string searching algorithm, Tight comparison bounds for the string prefix-matching problem, Faster string matching based on hashing and bit-parallelism, The Möbius function of factor order, On approximate jumbled pattern matching in strings, Fast searching in packed strings, Pattern matching in pseudo real-time, Approximate pattern matching with the \(L_1\), \(L_2\) and \(L_\infty\) metrics, On some operations on strings suggested by gene assembly in ciliates, A quick tour on suffix arrays and compressed suffix arrays, Linear time algorithms for generalizations of the longest common substring problem, Linear-time computation of local periods, Bounded hairpin completion, Characteristic Sturmian words are extremal for the critical factorization theorem, La reconnaissance des facteurs d'un mot dans un texte, Simple and efficient string matching with k mismatches, A theory of ultimately periodic languages and automata with an application to time granularity, On the size of Boyer-Moore automata, Palindromic rich words and run-length encodings, Computationally secure pattern matching in the presence of malicious adversaries, Gray code orders for \(q\)-ary words avoiding a given factor, Efficient indexing algorithms for one-dimensional discretely-scaled strings, Computing a longest common subsequence for a set of strings, An analytical comparison of two string searching algorithms, Essence of generalized partial computation, Optimal superprimitivity testing for strings, Derivation of efficient logic programs by specialization and reduction of nondeterminism, A complete mechanization of correctness of a string-preprocessing algorithm, Regular algebra applied to language problems
