惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

J
Java Code Geeks
美团技术团队
Microsoft Azure Blog
Microsoft Azure Blog
V
Visual Studio Blog
Jina AI
Jina AI
博客园_首页
M
MIT News - Artificial intelligence
D
DataBreaches.Net
L
LangChain Blog
宝玉的分享
宝玉的分享
F
Fortinet All Blogs
A
About on SuperTechFans
月光博客
月光博客
Stack Overflow Blog
Stack Overflow Blog
Google DeepMind News
Google DeepMind News
N
Netflix TechBlog - Medium
Y
Y Combinator Blog
腾讯CDC
Vercel News
Vercel News
雷峰网
雷峰网
GbyAI
GbyAI
aimingoo的专栏
aimingoo的专栏
阮一峰的网络日志
阮一峰的网络日志
博客园 - 【当耐特】

math updates on arXiv.org

Coupling-Robust Accuracy in Multiphysics Physics Informed Neural Networks via Kronecker-Preconditioned Optimization Non-normal spectral signatures of instability in neural network training dynamics Optimization of randomized neural networks for transfer operator approximation Selective Ambulance Dispatch Under Contextual Travel-Time Uncertainty LLAMA LIMA: A Living Meta-Analysis on the Effects of Generative AI on Learning Mathematics Neural Flow Operators can Approximate any Operator: Abstract Frameworks and Universal Approximations LLMs as Noisy Channels: A Shannon Perspective on Model Capacity and Scaling Laws On the Stability of Spherical Hellinger-Kantorovich Flows and Their Implications for Differential Privacy Training-Free Looped Transformers Move on Muon : A Hamiltonian probability gradient flow perspective of Muon optimizer Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries Asymmetric Scaling Laws from Sparse Features Is Dimensionality a Barrier for Retrieval Models? RA-DCA: A Randomized Active-Set DCA for Directional Stationarity in Max-Structured DC Programs Commutator-Induced Uncertainty in VAEs Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them Sparse In-Network Learning via Shortest-Path Backpropagation and Finite-Rate Gating Instance-Optimal Estimation with Multiple LLM Judges on a Budget Entropy Equivalence Testing Expand More, Shrink Less: Shaping Effective-Rank Dynamics for Dense Scaling in Recommendation Any-Dimensional Invariant Universality Operationalizing Individual Fairness via Gradient Descent and Bradley-Terry Models Anytime Training with Schedule-Free Spectral Optimization Diffusion-based Denoising Beats Vanilla Score Matching in Parameter Estimation: A Theoretical Explanation Resilience Characterization of AI-Native Wireless Receivers via Persistent Homology The General Theory of Localization Methods Group-Algebraic Tensors: Provably-optimal Equivariant Learning and Physical Symmetry Discovery General Lower Bounds for Differentially Private Federated Learning with Arbitrary Public-Transcript Interactions PilotWiMAE: Pilot-Native Representation Learning for Wireless Channels Proximal basin hopping: global optimization with guarantees
Synchronization of strongly connected partial DFAs and pr...
Mikhail V. Berlinkov, Robert Ferens, Andrew Ryzhikov, Marek Szyk · 2021-01-13 · via math updates on arXiv.org

We study synchronizing partial DFAs, which extend the classical concept of synchronizing complete DFAs and are a special case of synchronizing unambiguous NFAs. A partial DFA is called synchronizing if it has a word (called a \emph{reset word}) whose action brings a non-empty subset of states to a unique state and is undefined for all other states. The class of strongly connected partial DFAs is precisely the class of DFAs recognizing the Kleene star of prefix codes. While in the general case the problem of checking whether a partial DFA is synchronizing is PSPACE-complete, we show that in the strongly connected case, this problem can be efficiently reduced to the same problem for a complete DFA. Using combinatorial, algebraic, and formal languages methods, we develop techniques that relate main synchronization problems for strongly connected partial DFAs to the same problems for complete DFAs. In particular, this includes the Černý and the rank conjectures, the problem of finding a reset word, and upper bounds on the length of the shortest reset words of literal automata of finite prefix codes. We conclude that solving fundamental synchronization problems is equally hard in both models, as an essential improvement of the results for one model implies an improvement for the other.