魔鬼在游行
发表于 2025-3-25 04:46:55
,On the Power of Recursive Word-Functions Without Concatenation,ds allows to address words directly and not through some integer encoding (of exponential size). Considering alphabets with at least two symbols allows to relate simply and naturally to complexity theory. Indeed, the polynomial-time complexity class (as well as . and exponential time) corresponds to
投射
发表于 2025-3-25 08:07:50
http://reply.papertrans.cn/27/2683/268288/268288_22.png
口诀法
发表于 2025-3-25 12:21:56
,Nearly ,-Universal Words - Investigating a Part of Simon’s Congruence, of scattered factors (also known as subwords or subsequences), which are parts of the word in the correct order but not necessarily consecutive, e.g., . is a scattered factor of . but . is not. Following the idea of scattered factor .-universality (also known as .-richness), we investigate nearly .
熔岩
发表于 2025-3-25 19:19:12
State Complexity of Binary Coded Regular Languages,ton (DFA) . with . states recognizing a language . over ., we consider the problem of how many states we need for an automaton . that decides membership in ., the binary coded version of .. Namely, . accepts binary inputs belonging to . and rejects binary inputs belonging to ., where . is the comple
allude
发表于 2025-3-25 23:42:39
http://reply.papertrans.cn/27/2683/268288/268288_25.png
威胁你
发表于 2025-3-26 03:11:38
http://reply.papertrans.cn/27/2683/268288/268288_26.png
存在主义
发表于 2025-3-26 05:57:08
,Operations on Subregular Languages and Nondeterministic State Complexity,combinational, finitely generated left ideal, group, star, comet, two-sided comet, ordered, and power-separating languages, and consider the operations of intersection, union, concatenation, power, Kleene star, reversal, and complementation. We get the exact complexity in all cases, except for compl
BLINK
发表于 2025-3-26 08:31:23
http://reply.papertrans.cn/27/2683/268288/268288_28.png
听写
发表于 2025-3-26 15:03:20
http://reply.papertrans.cn/27/2683/268288/268288_29.png
urethritis
发表于 2025-3-26 18:28:23
Lazy Regular Sensing,uitively, the sensing cost quantifies the detail in which a random input word has to be read in order to decide its membership in the language, when the input letters composing the word are truth assignments to a finite set of .. We introduce the notion of ., where the signals are not sensed simulta