Decimate
发表于 2025-3-30 10:06:33
http://reply.papertrans.cn/28/2703/270231/270231_51.png
使成波状
发表于 2025-3-30 15:05:16
On Decision Problems for Simple and Parameterized MachinesWe introduce what we believe to be the simplest known classes of language acceptors for which we can prove that decision problems (like universe, disjointness, containment, etc.) are undecidable. We also look at classes with undecidable decision problems and show that the problems become decidable for the “parameterized” versions of the machines.
BLANC
发表于 2025-3-30 20:35:39
Computing Blocker Sets for the Regular Post Embedding ProblemBlocker and coblocker sets are regular languages involved in the algorithmic solution of the Regular Post Embedding Problem. We investigate the computability of these languages and related decision problems.
essential-fats
发表于 2025-3-31 00:20:45
Reaction Systems: A Model of Computation Inspired by Biochemistryture. In other words, natural computing investigates models and computational techniques inspired by nature as well as it investigates, in terms of information processing, processes taking place in nature.
OMIT
发表于 2025-3-31 01:45:45
On a Conjecture by Carpi and D’Alessandros for synchronizing automata with . states. We refute this conjecture as well as a related conjecture by Rystsov and suggest a weaker version that still suffices to achieve a quadratic upper bound.
畏缩
发表于 2025-3-31 08:59:39
http://reply.papertrans.cn/28/2703/270231/270231_56.png
FLIT
发表于 2025-3-31 10:32:58
Kleene and Büchi Theorems for Weighted Automata and Multi-valued Logics over Arbitrary Bounded Latti and for finite and infinite words. This extends classical results of Kleene and Büchi to arbitrary bounded lattices, without any distributivity assumption that is fundamental in the theory of weighted automata over semirings. In fact, we obtain these results for large classes of strong bimonoids which properly contain all bounded lattices.
粘连
发表于 2025-3-31 17:07:10
Minimization of Deterministic Bottom-Up Tree Transducerss based on a sequence of normalizing transformations which, among others, guarantee that non-trivial output is produced as early as possible. For a deterministic bottom-up transducer where every state produces either none or infinitely many outputs, the minimal transducer can be constructed in polynomial time.
fodlder
发表于 2025-3-31 18:00:01
https://doi.org/10.1007/978-3-642-14455-4automata theory; complexity; computability; game theory; infinite words; inite automata; logic; tar; tempora