A Graph-Theoretic Characterization of the $\text{PV}_{\text{chunk}}$ Class of Synchronizing Primitives

DOI10.1137/0206008zbMath0349.68022OpenAlexW2000506665MaRDI QIDQ4120130

Yechezkel Zalcstein, Peter B. Henderson

Publication date: 1977

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0206008

Mathematics Subject Classification ID

General topics in the theory of software (68N01) Algorithms in computer science (68W99)

Related Items

Total matchings and total coverings of threshold graphs, Split graphs, No threshold graphs are cospectral, An \(O(n^3)\) time algorithm for recognizing threshold dimension 2 graphs, Can transitive orientation make sandwich problems easier?, Validity of Akbari's energy conjecture for threshold graphs, Longest cycles in threshold graphs, Seidel spectrum of threshold graphs, Efficient Computation of the Characteristic Polynomial of a Threshold Graph, Complex Pythagorean fuzzy threshold graphs with application in petroleum replenishment, On the distance spectra of threshold graphs, Maximum Laplacian energy among threshold graphs, Matroids arisen from matrogenic graphs, \(\lambda\)-coloring matrogenic graphs, Clique Partitions of Chordal Graphs, Threshold Dimension of Graphs, The role of the anti-regular graph in the spectral analysis of threshold graphs, Characterizing threshold graphs with \(k\) main signless Laplacian eigenvalues, On the spectrum of threshold graphs, An explicit formula for the distance characteristic polynomial of threshold graphs, The signless Laplacian spectral radius of graphs with a prescribed number of edges, Eccentricity spectral radius of \(t\)-clique trees with given diameter, Generating \(I\)-eigenvalue free threshold graphs, Connected graphs of fixed order and size with maximal \(A_\alpha \)-index: the one-dominating-vertex case, Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs, Eigenvalue location in threshold graphs, On dynamic threshold graphs and related classes, Ferrers digraphs and threshold graphs, On 2-switches and isomorphism classes, Competitive evaluation of threshold functions in the priced information model, Eigenvalues and energy in threshold graphs, Graphs and degree sequences. I, A conjecture on the eigenvalues of threshold graphs, Recognizing strict 2-threshold graphs in O(m) time, An \(O(n^ 3)\) recognition algorithm for bithreshold graphs, Efficient computation of the characteristic polynomial of a threshold graph, On the eigenvalues distribution in threshold graphs, Bounds on Threshold Dimension and Disjoint Threshold Coverings, Laplacian controllability classes for threshold graphs, On the normalized spectrum of threshold graphs, Competitive Boolean function evaluation: beyond monotonicity, and the symmetric case, The polytope of degree sequences, Spectral characterizations of anti-regular graphs, The completion of a classification for maximal nonhamiltonian Burkard-Hammer graphs, Trivially perfect graphs, Forbidden subgraphs of power graphs, Fully Dynamically Maintaining Minimal Integral Separator for Threshold and Difference Graphs, The size of chordal, interval and threshold subgraphs, Cubicity of threshold graphs, Group-annihilator graphs realised by finite abelian groups and its properties, On the eccentricity spectra of threshold graphs, A necessary condition for maximal nonhamiltonian Burkard-Hammer graphs, ON THE PAIRWISE COMPATIBILITY PROPERTY OF SOME SUPERCLASSES OF THRESHOLD GRAPHS, Note on chromatic polynomials of the threshold graphs, Threshold hypergraphs, Once more on matrogenic graphs