SIT
发表于 2025-3-28 18:20:19
Undecidability of Weak Bisimilarity for PA-ProcessesWe prove that the problem whether two PA-processes are weakly bisimilar is undecidable. We combine several proof techniques to provide a reduction from Post’s correspondence problem to our problem: existential quantification technique, masking technique and deadlock elimination technique.
STENT
发表于 2025-3-28 22:07:59
http://reply.papertrans.cn/28/2703/270244/270244_42.png
蛤肉
发表于 2025-3-28 23:15:37
http://reply.papertrans.cn/28/2703/270244/270244_43.png
Evacuate
发表于 2025-3-29 03:07:44
978-3-540-40431-6Springer-Verlag Berlin Heidelberg 2003
男学院
发表于 2025-3-29 10:32:40
http://reply.papertrans.cn/28/2703/270244/270244_45.png
AV-node
发表于 2025-3-29 12:47:48
http://reply.papertrans.cn/28/2703/270244/270244_46.png
Functional
发表于 2025-3-29 19:03:19
Rousseau, Schiller, Herder, Heinsenumber of transitions) of the resulting automata, and on the time complexity of the transformation..We show how recent developments [.],[.] have improved the size of the resulting automaton from .(..) to .(.(log .).), and even .(. log .) for bounded alphabet size (where . is the size of the regular
Allure
发表于 2025-3-29 20:13:54
Rousseau, Schiller, Herder, Heinsenown linear time algorithm for quadratic word equations with length constraints to cope with involutions. Finally, we show that the same linear-time result cannot be expected for trace equations. We obtain an NP-hardness result.
他姓手中拿着
发表于 2025-3-30 02:00:30
Rousseau, Schiller, Herder, Heinsetical colors in their adjacent edges. A snake is a non-overlapping sequence of tiles. We show that it is undecidable if such snakes or cycles are possible using copies of tiles from a given finite tile collection.
Immobilize
发表于 2025-3-30 04:32:00
Bernhard Böschenstein,Ulrich Gaiers. A DNA strand can be viewed as a string over a four letter alphabet (the four deoxyribonucleotides), therefore we can model DNA computation within the framework of formal language theory. In spite of a vast literature on splicing systems, briefly surveyed here, a few problems related to their comp