animated
发表于 2025-3-23 13:07:39
Recognizing Shuffled Languagesan recognition, and natural language processing. We study the complexity of the membership problem for such models, i.e., how difficult it is to determine if a string belongs to a language or not. In particular, we investigate how interleaving can be introduced into models that capture the context-free languages.
HEDGE
发表于 2025-3-23 15:04:20
http://reply.papertrans.cn/59/5811/581013/581013_12.png
Coordinate
发表于 2025-3-23 21:47:43
http://reply.papertrans.cn/59/5811/581013/581013_13.png
唤起
发表于 2025-3-24 02:15:48
Mutation Systemsutomaton simulation shows that in this framework, universal computation is possible and the question of whether one string can evolve into another is undecidable. We also analyze the efficiency of the finite state machine simulation assuming random point mutations.
adulterant
发表于 2025-3-24 04:24:28
http://reply.papertrans.cn/59/5811/581013/581013_15.png
drusen
发表于 2025-3-24 06:38:10
http://reply.papertrans.cn/59/5811/581013/581013_16.png
aphasia
发表于 2025-3-24 11:37:31
A Simple and Efficient Universal Reversible Turing Machineersibilizing any existing universal machine. The interpretive overhead of the URTM is limited to a (program dependent) constant factor slowdown, with no other complexity-wise cost . time and space. The URTM is also able to function as an . for RTMs at no asymptotic cost, simply by reversing the string representing the interpreted machine.
运动的我
发表于 2025-3-24 17:25:49
Unary Pattern Avoidance in Partial Words Dense with Holesles. We define the concept of hole sparsity, a measure of the frequency of holes in a partial word, and determine the minimum hole sparsity for all unary patterns in the context of trivial and non-trivial avoidability.
外面
发表于 2025-3-24 21:23:19
http://reply.papertrans.cn/59/5811/581013/581013_19.png
Melodrama
发表于 2025-3-25 02:00:18
The Complexity of Request-Response Gamesmes played on DAGs, and .-complete or .-complete if there is only one player (depending on whether he wants to enforce or spoil the request-response condition)..We also present near-optimal bounds on the memory needed to design winning strategies for each player, in each case.