松紧带
发表于 2025-3-26 21:02:07
Mutually Accepting Capacitated Automata,. of CAs and view them as recognizers of . – sets of multisets of words, where a multiset . of words is in the multi-language of a CA . if all the words in . can be mutually accepted by .: the multiset of runs on all the words in . together respects the bounds induced by the capacities. Thus, capaci
GUEER
发表于 2025-3-27 01:29:40
Bad Pictures: Some Structural Properties Related to Overlaps,s a bit-to-bit transformation from . to . such that any picture in the intermediate steps is .-free. Such transformation is called .-.. A binary picture is . if it is not good. These notions generalize to pictures the corresponding ones for strings. We study some properties of bad binary pictures in
fatuity
发表于 2025-3-27 08:26:05
http://reply.papertrans.cn/27/2683/268291/268291_33.png
essential-fats
发表于 2025-3-27 10:07:59
Crisp-Determinization of Weighted Tree Automata over Additively Locally Finite and Past-Finite Mono of the underlying weight algebra; weights different from these units may only appear at the root of the given input tree. A weighted tree automaton is crisp-determinizable if there exists an equivalent crisp-deterministic one. We prove that it is decidable whether weighted tree automata over additi
lattice
发表于 2025-3-27 14:34:50
http://reply.papertrans.cn/27/2683/268291/268291_35.png
Acetaminophen
发表于 2025-3-27 17:58:31
State Complexity Bounds for the Commutative Closure of Group Languages,is bounded by the number of states of the original automaton, raised to the power of the alphabet size, times the product of the order of the letters, viewed as permutations of the state set. This gives the asymptotic state bound ., if the original regular language is accepted by an automaton with .
Filibuster
发表于 2025-3-27 22:05:11
Multiple Concatenation and State Complexity (Extended Abstract),ure. Then we use slightly modified Maslov’s automata to get witnesses over a .-letter alphabet which solves an open problem stated by Caron et al. . We prove that for ., the ternary alphabet is optimal. We also obtain lower bounds . and . in the binary and ternary c
Acetaldehyde
发表于 2025-3-28 05:54:57
Combining Limited Parallelism and Nondeterminism in Alternating Finite Automata, (AFA), counts the number of branches which do not need to be traversed in an accepting computation (respectively, the maximum number of branches which can be ignored in any computation tree of the AFA). We also define the combined width (respectively, the maximal combined width), by combining this
条街道往前推
发表于 2025-3-28 07:28:33
Longer Shortest Strings in Two-Way Finite Automata,FA) can be at least . symbols long, improved to . in their latest contribution. The lower bound was obtained using “direction-determinate” 2DFA, which always remember their direction of motion at the last step, and used an alphabet of size .. In this paper, the method of Dobronravov et al. is extend
十字架
发表于 2025-3-28 13:59:52
Iterated Uniform Finite-State Transducers: Descriptional Complexity of Nondeterminism and Two-Way Ms on the output of the previous one. We consider devices with one-way motion and two-way motion, i.e., sweeps are either from left to right only, or alternate from left to right and from right to left. In addition, devices may work deterministically or nondeterministically. Here, we restrict to stud