CAJ
发表于 2025-3-26 22:38:55
The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE—Complete constraints, i.e., such that a possible solution has to respect a specification given by a rational language. Our main result states that the existential theory of equations with rational constraints in free groups is PSPACE-complete.
切掉
发表于 2025-3-27 04:13:52
http://reply.papertrans.cn/87/8604/860324/860324_32.png
GIDDY
发表于 2025-3-27 08:11:03
http://reply.papertrans.cn/87/8604/860324/860324_33.png
壮观的游行
发表于 2025-3-27 10:51:01
Scalable Sparse Topologies with Small Spectrum theoretical interest and also of practical impact. Graphs with small spectra exhibit many symmetry properties and are well suited as interconnection topologies. Es- pecially load balancing can be done on such interconnection topologies in a small number of steps. In this paper we are interested in
Exuberance
发表于 2025-3-27 15:48:10
Myhill-Nerode Relations on Automatic Systems and the Completeness of Kleene Algebra automata can. The Brzozowski derivative on an algebra of polynomials over a Kleene algebra gives rise to a triangular automatic system that can be solved using these methods. This provides an alternative method for proving the completeness of Kleene algebra.
CRAMP
发表于 2025-3-27 17:49:31
Matching Polygonal Curves with Respect to the Fréchet Distance points for the Fréchet distance. Furthermore we give a new reference point that is substantially better than all known reference points for the Hausdorff distance. These results yield a (1 + ∈)-approximation algorithm for the matching problem that has runtime .(∈..).
招待
发表于 2025-3-28 01:39:49
http://reply.papertrans.cn/87/8604/860324/860324_37.png
oxidize
发表于 2025-3-28 04:24:14
Scalable Sparse Topologies with Small Spectrumgraphs with maximal degree .(log .), where . is the number of vertices, and with a small number of distinct eigenvalues. Our goal is to find scalable families of such graphs with polyloga- rithmic spectrum in the number of vertices. We present also the eigenvalues of the Butterfly graph.
CRP743
发表于 2025-3-28 08:27:25
On Presburger Liveness of Discrete Timed Automatath of .. These results might give insights into the cor- responding problems for timed automata over dense domains, and help in the definition of a fragment of linear temporal logic, augmented with Presburger conditions on configurations, which is decidable for model checking timed automata.
CHURL
发表于 2025-3-28 14:24:56
On the Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributionalis proper unless . = .. (2) . contains Dist . , but it is not contained in Ave . unless Dist . ≠ Ave .. (3) . has a ≤..-complete set. (4) . has a ≤..-complete set that is not ≤..-complete unless . = .. This shows that under the assumption that . ≠ . , the two complete- ness notions differ on some non-trivial subclass of Dist ..