Isomorphism Testing for Graphs, Semigroups, and Finite Automata are Polynomially Equivalent Problems
From MaRDI portal
Publication:4162481
DOI10.1137/0207023zbMath0381.68042OpenAlexW2048172960MaRDI QIDQ4162481
Publication date: 1978
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0207023
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)
Related Items
Testing for grammatical coverings, The complexity of Boolean matrix root computation, The isomorphism problem for varieties generated by a two-element algebra, Nominal Unification and Matching of Higher Order Expressions with Recursive Let, Complexity results in graph reconstruction, On the complexity of graph reconstruction, On the Uniform Random Generation of Non Deterministic Automata Up to Isomorphism, Construction of an effective algorithm to find the isomorphism of two simple finite semigroups, Concerning the complexity of deciding isomorphism of block designs, Isomorphism testing via polynomial-time graph extensions, The complexity of computing the automorphism group of automata and related problems, The complexity of manipulative attacks in nearly single-peaked electorates, Perfect matching for regular graphs is \(AC^ 0\)-hard for the general matching problem, Graph isomorphism, general remarks, The complexity of homomorphism factorization, Theoretical and computational advances for network diversion, INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS, Subcomplete generalizations of graph isomorphism, Computational complexity of problems for deterministic presentations of sofic shifts, Graph isomorphism problem, Testing homotopy equivalence is isomorphism complete
