tooth-decay
发表于 2025-3-28 17:25:46
Two-Pass Greedy Regular Expression Parsingme .(.) for REs of size . and input strings of size . and outputs a compact bit-coded parse tree representation. It improves on previous algorithms by: operating in only 2 passes; using only .(.) words of random-access memory (independent of .); requiring only .. bits of sequentially written and rea
jet-lag
发表于 2025-3-28 21:16:55
Universal Witnesses for State Complexity of Basic Operations Combined with Reversalr bounds for the symmetric differences and differences of such languages. We prove that the previously discovered bounds for union, intersection, concatenation and star of such languages can all be met by the recently introduced universal witness and its variants.
Graves’-disease
发表于 2025-3-29 01:54:51
http://reply.papertrans.cn/47/4626/462527/462527_43.png
CLAM
发表于 2025-3-29 06:21:46
A Uniformization Theorem for Nested Word to Word Transductionsation can be uniformized by a functional relation from the same class, implemented by an unambiguous transducer. We give an exponential upper bound on the state complexity of the uniformization, improving a previous doubly exponential upper bound. Our construction generalizes a classical constructio
Vertebra
发表于 2025-3-29 10:13:35
http://reply.papertrans.cn/47/4626/462527/462527_45.png
Occupation
发表于 2025-3-29 13:06:12
Implementation Concepts in Vaucanson 2of mathematical objects. Initiated ten years ago, several shortcomings were discovered along the years, especially problems related to code complexity and obfuscation as well as performance issues. This paper presents the concepts underlying ., a complete rewrite of the platform that addresses these
Redundant
发表于 2025-3-29 16:16:12
A Completion Algorithm for Lattice Tree Automatapose Lattice Tree Automata, an extended version of tree automata to represent complex data domains and their related operations in an efficient manner. Moreover, we introduce a new completion-based algorithm for computing the possibly infinite set of reachable states in a finite amount of time. This
adulterant
发表于 2025-3-29 23:00:23
Approximate Matching between a Context-Free Grammar and a Finite-State Automatonguages. We in particular consider three different gap cost models, linear, affine and concave models, that are crucial for finding a proper alignment between two bio sequences. We design efficient algorithms for computing the edit-distance between a CFG and an FA under these gap cost models. The tim
和平主义者
发表于 2025-3-30 02:04:32
Brzozowski’s Minimization Algorithm—More Robust than Expectedl deterministic finite automaton by applying reversal and power-set construction twice. Although this is an exponential algorithm because of the power-set construction, it performs well in experimental studies compared to efficient .(.log.) minimization algorithms. Here we show how to slightly enhan
Entropion
发表于 2025-3-30 04:40:30
Some Decision Problems Concerning NPDAs, Palindromes, and Dyck Languagesther the NPDA makes a bounded number of stack reversals (over all accepting inputs) and show that this problem is undecidable even when the NPDA is only 2-ambiguous. We consider the same problem for counter machines (i.e., whether the counter makes a bounded number of reversals) and show that it is