思想上升
发表于 2025-3-25 04:06:49
Aperiodic String Transducers,. to copyless ., and (.) from .-bounded to 1-bounded .. We give the complexity of each construction and also prove that they preserve the aperiodicity of transducers. As corollaries, we obtain that . definable string-to-string functions are equivalent to . whose transition monoid is finite and aperiodic, and to aperiodic copyless ..
ACRID
发表于 2025-3-25 07:55:52
Alternating Demon Space Is Closed Under Complement and Other Simulations for Sublogarithmic Space,nown inclusion, stating that .. . ., i.e., the alternating space is closed under complement. This simulation does not depend on whether .(.) is above . nor on whether the original machine gets into infinite loops, which solves a long-standing open problem.
AUGUR
发表于 2025-3-25 12:04:44
http://reply.papertrans.cn/28/2703/270241/270241_23.png
APEX
发表于 2025-3-25 18:13:05
http://reply.papertrans.cn/28/2703/270241/270241_24.png
我们的面粉
发表于 2025-3-25 23:09:03
,-Abelian Equivalence and Rationality,nce by rewriting, so-called .-switching. We show that the set of lexicographically least representatives of equivalence classes is a regular language. From this we infer that the sequence of the numbers of equivalence classes is .-rational. We also show that the set of words defining .-abelian singleton classes is regular.
偶像
发表于 2025-3-26 02:28:46
,Schützenberger Products in a Category,er), ordered monoids (Pin), idempotent semirings (Klíma and Polák), and algebras over a field (Reutenauer). In addition, assuming that . is part of a Stone-type duality, we derive a characterization of the languages recognized by Schützenberger products.
拥挤前
发表于 2025-3-26 05:01:06
Both Ways Rational Functions,rational relations, while those of the latter define an a priori really different family. We characterize the partial functions that are in the intersection of the two families. We state a conjecture for the intersection for general, nonfunctional, relations.
变形
发表于 2025-3-26 09:46:08
Degrees of Infinite Words, Polynomials and Atoms,ges are well-understood, very little is known about the power of automata to transform infinite words..We use methods from linear algebra and analysis to show that there is an infinite number of atoms in the transducer degrees, that is, minimal non-trivial degrees.
舰旗
发表于 2025-3-26 12:49:44
Non-regular Maximal Prefix-Free Subsets of Regular Languages,ntext-free, it has a MPFS which is recursive but not context-sensitive, and it has a MPFS which is not recursively enumerable..We show that no regular language has a MPFS which is recursively enumerable but not recursive. Finally, for any regular language we can decide whether or not it has a context-free non-regular MPFS.
谁在削木头
发表于 2025-3-26 20:02:16
https://doi.org/10.1007/978-3-662-66651-7new class called bounded-balance MPDAs. These MPDAs allow for infinitely deep nesting/nesting intersection, as long as the nesting depth differences within each scope stay within the balance bound. We compare our contributions to various related MPDAs and ambiguity detection methods.