Breach
发表于 2025-3-28 15:38:27
Descriptional and Computational Complexity of the Circuit Representation of Finite Automata,complexity, obtain upper and lower bounds which differ only by a factor of 4 for a Binary input alphabet. Also we prove that many simple operations (determining if a state is reachable or if an automaton is minimal) are PSPACE-complete for DFA given in circuit representation.
袖章
发表于 2025-3-28 21:26:01
A General Class of Monoids Supporting Canonisation and Minimisation of (Sub)sequential Transducers,hese problems can be efficiently solved for a large class of monoids that includes the free monoids, tropical monoid, and groups, and is closed under Cartesian Product. We describe this class of monoids in terms of five simple axioms. The first four of them seem to be natural. For the last one, we show that it is also necessary.
Abduct
发表于 2025-3-29 01:19:21
http://reply.papertrans.cn/59/5811/581021/581021_43.png
Ganglion
发表于 2025-3-29 03:19:14
Measuring Closeness Between Cayley Automatic Groups and Automatic Groups,l characteristic. We characterize Cayley automatic groups which are not automatic in terms of this numerical characteristic and then study it for the lamplighter group, the Baumslag–Solitar groups and the Heisenberg group.
projectile
发表于 2025-3-29 07:26:34
http://reply.papertrans.cn/59/5811/581021/581021_45.png
智力高
发表于 2025-3-29 12:27:56
http://reply.papertrans.cn/59/5811/581021/581021_46.png
Myelin
发表于 2025-3-29 19:35:58
Language and Automata Theory and Applications978-3-319-77313-1Series ISSN 0302-9743 Series E-ISSN 1611-3349
平息
发表于 2025-3-29 21:35:52
Constraint Satisfaction Problems: Complexity and Algorithms,In this paper we briefly survey the history of the Dichotomy Conjecture for the Constraint Satisfaction problem, that was posed 25 years ago by Feder and Vardi. We outline some of the approaches to this conjecture, and then describe an algorithm that yields an answer to the conjecture.
眼界
发表于 2025-3-30 00:25:06
http://reply.papertrans.cn/59/5811/581021/581021_49.png
handle
发表于 2025-3-30 07:56:55
http://reply.papertrans.cn/59/5811/581021/581021_50.png