2016/03/09 by Jochen Burghardt, Burghardt, Jochen
Computer Science · #68Q45 #Algorithms and Data Compression #F.4.2 #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Natural Language Processing Techniques #acm:68Q45 #cs.FL #msc:68Q45 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1603.02928
26 pages; 3 figures. Originally published 23 Mar 2004 as "FIRST Reports 1/2004". Section 4 essentially describes Knuth's algorithm from his paper "A Generalization of Dijkstra's Algorithm" (Information Processing Letters, Vol.6, No.1, p.1-5, 1977); I wasn't aware of its existence at that time
arxiv created 2016/03/09 · openalex publication_date 2016/03/09 · arxiv updated 2016/03/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a general framework to define an application-dependent weight measure on terms that subsumes e.g. total simplification orderings, and an O(n log n) algorithm for the simultaneous computation of the minimal weight of a term in the language of each nonterminal of a regular tree grammar, based on Barzdins' liquid-flow technique.