scientific article

zbMath0301.68027MaRDI QIDQ4055156

Michael S. Paterson, Michael J. Fischer

Publication date: 1974

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) General topics in the theory of software (68N01) Algorithms in computer science (68W99)

Related Items

Combinatorial properties of Fibonacci partial words and arrays, An acceleration of FFT-based algorithms for the match-count problem, Squareable Words, An aperiodicity problem for multiwords, Secure parameterized pattern matching, Computing Primitively-Rooted Squares and Runs in Partial Words, On the average-case complexity of pattern matching with wildcards, Lyndon partial words and arrays with applications, A Black Box for Online Approximate Pattern Matching, Compact suffix automata representations for searching long patterns, Multi-pattern matching algorithm with wildcards based on bit-parallelism, Efficient string matching on packed texts, Unnamed Item, Unnamed Item, A Simple Algorithm for Approximating the Text-To-Pattern Hamming Distance, Algorithms, Towards Optimal Approximate Streaming Pattern Matching by Matching Multiple Patterns in Multiple Streams, IDPM: An Improved Degenerate Pattern Matching Algorithm for Biological Sequences, Efficient and Secure Generalized Pattern Matching via Fast Fourier Transform, State complexity of finite partial languages, Square-Free Partial Words with Many Wildcards, Unnamed Item, Unnamed Item, Optimal parallel algorithms for periods, palindromes and squares, Nearly optimal computations with structured matrices, Ternary Square-Free Partial Words with Many Wildcards, Unnamed Item, Approximating Approximate Pattern Matching, Elastic-Degenerate String Matching via Fast Matrix Multiplication, Faster Online Elastic Degenerate String Matching, Faster Evaluation of Subtraction Games, A matching algorithm in PMWL based on CluTree, New bounds and extended relations between prefix arrays, border arrays, undirected graphs, and indeterminate strings, Binary segmentation for matrix and vector operations, Two-dimensional pattern matching with rotations, Efficient special cases of pattern matching with swaps, Resource scheduling with variable requirements over time, Set intersection and sequence matching with mismatch counting, Permuted scaled matching, Polynomial division and its computational complexity, Computing covers using prefix tables, Simple deterministic wildcard matching, Sequential and parallel complexity of approximate evaluation of polynomial zeros, Bit-parallel string matching under Hamming distance in \(O(n\lceil m/w\rceil)\) worst case time, Pattern matching with don't cares and few errors, Parallel string matching with k mismatches, Exploiting pseudo-locality of interchange distance, Efficient matching of nonrectangular shapes., Data structures and algorithms for approximate string matching, Complexity, combinatorial group theory and the language of palutators, A logarithmic Boolean time algorithm for parallel polynomial division, On pattern matching with \(k\) mismatches and few don't cares, Optimal and nearly optimal algorithms for approximating polynomial zeros, The approximate swap and mismatch edit distance, A filtering algorithm for \(k\)-mismatch with don't cares, Pattern matching with wildcards using words of shorter length, Covering problems for partial words and for indeterminate strings, Computing primitively-rooted squares and runs in partial words, Efficient pattern matching in degenerate strings with the Burrows-Wheeler transform, Longest common substring with approximately \(k\) mismatches, Matching a set of strings with variable length don't cares, Algorithms for path-constrained sequence alignment, Indeterminate string inference algorithms, Nearly optimal refinement of real roots of a univariate polynomial, Overlap matching., A simplified proof of the real-time recognizability of palindromes on Turing machines, Pattern matching in the Hamming distance with thresholds, Linear-time string-matching using only a fixed number of local storage locations, Finding patterns and periods in Cartesian tree matching, Towards optimal packed string matching, String matching with up to \(k\) swaps and mismatches, A lower-variance randomized algorithm for approximate string matching, Pattern matching with address errors: rearrangement distances, Parameterized matching with mismatches, A new approach to regular \& indeterminate strings, An algorithmic toolbox for periodic partial words, Fast profile matching algorithms - A survey, A note on the subtree isomorphism for ordered trees and related problems, On string matching with mismatches, Indeterminate strings, prefix arrays \& undirected graphs, Simple tree pattern matching for trees in the prefix bar notation, Parallel detection of all palindromes in a string, Streaming pattern matching with \(d\) wildcards, Generalized function matching, Fast average-case pattern matching by multiplexing sparse tables, Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth, Fast pattern-matching on indeterminate strings, Necklaces, convolutions, and \(X+Y\), Motif patterns in 2D, Incremental discovery of the irredundant motif bases for all suffixes of a string in \(O(n^2\log n)\)time, Extracting string motif bases for quorum higher than two, String indexing for patterns with wildcards, Approximate pattern matching with the \(L_1\), \(L_2\) and \(L_\infty\) metrics, Exploiting word-level parallelism for fast convolutions and their applications in approximate string matching, Matching with don't-cares and a small number of mismatches, Efficient construction of maximal and minimal representations of motifs of a string, Two fast simulations which imply some fast string matching and palindrome-recognition algorithms, Parsing Boolean grammars over a one-letter alphabet using online convolution, A black box for online approximate pattern matching, Fast parallel and serial multidimensional approximate array matching, Parameterized matching on non-linear structures, Optimal extraction of motif patterns in 2D, A faster algorithm for matching a set of patterns with variable length don't cares, Regular languages of partial words, A new approach to the periodicity lemma on strings with holes, Maximal and minimal representations of gapped and non-gapped motifs of a string, Palindrome recognition in real time by a multitape Turing machine, Efficient computations of \(\ell _1\) and \(\ell _{\infty }\) rearrangement distances, Computational geometric aspects of rhythm, melody, and voice-leading, Faster pattern matching with character classes using prime number encoding, Extreme witnesses and their applications, Efficient pattern matching in elastic-degenerate strings, On special families of morphisms related to \(\delta \)-matching and don't care symbols, Computationally secure pattern matching in the presence of malicious adversaries, An algorithm for string matching with a sequence of don't cares, A faster algorithm for the computation of string convolutions using LZ78 parsing, Time-space-optimal string matching, Extracting approximate patterns, Fast on-line integer multiplication, Fast and practical approximate string matching, State complexity of partial word finite automata, Approximate swapped matching., Squares and primitivity in partial words, Approximate periodicity, Inferring an indeterminate string from a prefix graph, On the state complexity of partial word DFAs, Fast algorithms for approximately counting mismatches, Recent advances in text-to-pattern distance algorithms, The derivation of on-line algorithms, with an application to finding palindromes, State complexity of finite partial languages, Approximate congruence in nearly linear time