Using multiset discrimination to solve language processing problems without hashing

DOI10.1016/0304-3975(94)00183-JzbMath0874.68165OpenAlexW2086323458MaRDI QIDQ673099

Robert Paige, Jiazhen Cai

Publication date: 28 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(94)00183-j

zbMATH Keywords

hashinglanguage processing problems

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

From regular expressions to DFA's using compressed NFA's, Generic top-down discrimination for sorting and partitioning in linear time, Reordering columns for smaller indexes, Constant-time tree traversal and subtree equality check for grammar-compressed trees, Efficient and flexible matching of recursive types, An NSF proposal

Uses Software

• SETL

Cites Work

• A class of algorithms which require nonlinear time to maintain disjoint sets
• A linear time solution to the single function coarsest partition problem
• Minimisation of acyclic deterministic automata in linear time
• Linear unification
• Universal classes of hash functions
• Three Partition Refinement Algorithms
• Variations on the Common Subexpression Problem
• Pattern Matching in Trees
• An algorithm for reduction of operator strength
• High level iterators and a method for automatically designing data structure representation
• Depth-First Search and Linear Graph Algorithms
• A Theorem on Boolean Matrices
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item