REVIEW 5 cited by
State Complexity of the Set of Synchronizing Words for Circular Automata and Automata over Binary Alphabets
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
State Complexity of the Set of Synchronizing Words for Circular Automata and Automata over Binary Alphabets
read the original abstract
Most slowly synchronizing automata over binary alphabets are circular, i.e., containing a letter permuting the states in a single cycle, and their set of synchronizing words has maximal state complexity, which also implies complete reachability.Here, we take a closer look at generalized circular and completely reachable automata. We derive that over a binary alphabet every completely reachable automaton must be circular, a consequence of a structural result stating that completely reachable automata over strictly less letters than states always contain permutational letters. We state sufficient conditions for the state complexity of the set of synchronizing words of a generalized circular automaton to be maximal. We apply our main criteria to the family $\mathscr K_n$ of automata that was previously only conjectured to have this property.
Forward citations
Cited by 5 Pith papers
-
Bias at the Borderline: Who Gets the Benefit of the Doubt in Peer Review?
At ICLR, equally scored borderline papers from outside top-25 institutions are accepted less often, a gap concentrated in preprint-identifiable submissions; outcome tests find no evidence of a higher bar.
-
Completely Reachable Road Coloring
A digraph admits a completely reachable road coloring iff it is strongly connected, aperiodic, and every vertex subset has at least as many in-neighbors as vertices; the fixed-alphabet version is claimed NP-complete, ...
-
Judges matter more than papers in post-publication research assessment
Judge-level effects and judge-specific slopes explain 61% of variance in H1 Connect research quality ratings versus 7% for papers and journals combined.
-
AutoSupervision: Closing the Feedback Loop in Scientific Workflows with Grounded Revision Verification
On a new 8,790-instance benchmark built from Nature Communications review records, LLMs characterize reviewer concerns well (GPT-5.5: 0.754) but verify evidence-backed revision resolution poorly (best 0.501).
-
Completely Reachable Road Coloring
Digraphs admitting a completely reachable edge labeling are polynomial-time recognizable (NP-complete for fixed alphabet size), and digraphs where every labeling works are classified.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.