Gerontology
发表于 2025-3-25 07:12:55
http://reply.papertrans.cn/27/2683/268290/268290_21.png
热情的我
发表于 2025-3-25 09:40:21
,Operational State Complexity Revisited: The Contribution of Monsters and Modifiers,imal state complexity of the languages . where . are languages with given state complexities. We highlight two tools that have been developed in recent years and which theorise and summarise a large number of methods used since the 1970 s. A monster is an automaton where any function from states to
我要沮丧
发表于 2025-3-25 14:30:34
,Hypercubes and Isometric Words Based on Swap and Mismatch Distance,ming distance 1. We consider an edit distance based on swaps and mismatches, to which we refer as ., and define the . with edges linking words at tilde-distance 1. Then, we introduce and study some isometric subgraphs of the tilde-hypercube obtained by using special words called .. The subgraphs kee
龙虾
发表于 2025-3-25 17:57:53
,Defying Gravity and Gadget Numerosity: The Complexity of the Hanano Puzzle,em (a .-complete problem that is very convenient to prove the .-hardness of reversible games with pushing blocks). Direct use of this property introduces an explosion in the number of gadgets needed to show .-hardness, but we show how to bring that number from 32 down to only three in general, and d
能够支付
发表于 2025-3-25 22:45:07
http://reply.papertrans.cn/27/2683/268290/268290_25.png
Flu表流动
发表于 2025-3-26 02:21:12
,On Jaffe’s Pumping Lemma, Revisited, perspective. Jaffe’s pumping lemma is a necessary and sufficient condition for a language for being regular. In this way we improve a result of [.. A note on the pumping lemma for regular languages. ., 9(3):135–136, 1979] by showing that there is a regular language over the alphabet . of size at le
掺和
发表于 2025-3-26 05:29:12
http://reply.papertrans.cn/27/2683/268290/268290_27.png
Heterodoxy
发表于 2025-3-26 11:15:13
,The Word Problem for Finitary Automaton Groups,ops at an identity state. We show that, for this presentation of finite groups, the uniform word problem is .-complete. Here, the input consists of a finitary automaton together with a finite state sequence and the question is whether the sequence acts trivially on all input words. Additionally, we
庇护
发表于 2025-3-26 14:06:07
http://reply.papertrans.cn/27/2683/268290/268290_29.png
dominant
发表于 2025-3-26 19:08:45
,Complexity of Exclusive Nondeterministic Finite Automata,ed if there is exactly one accepting path in its computation tree. If there are none or more than one accepting paths, the input is rejected. It turns out that, from a descriptional complexity point of view, .s differ significantly from the known types of finite automata. In particular the state cos