Boolean Functions, Invariance Groups, and Parallel Complexity

DOI10.1137/0220036zbMath0734.68038OpenAlexW1969850363MaRDI QIDQ3361880

Peter Clote, Evangelos Kranakis

Publication date: 1991

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

Full work available at URL: https://ir.cwi.nl/pub/1619

zbMATH Keywords

Boolean functionspermutation groupparallel complexityregular languageabelian groupwreath productpumping lemmaclassification theorysymmetric Boolean functioncyclic- dihedral-, hyperoctahedral- groupsindex of a groupinvariance group of boolean functionPólya's cycle indexrepresentable group

Mathematics Subject Classification ID

Related Items (17)

On generalized \(P\)-reducible Finsler manifolds ⋮ On symmetric circuits and fixed-point logics ⋮ Linear symmetries of Boolean functions. ⋮ Labeled versus unlabeled distributed Cayley networks ⋮ Symmetry groups of Boolean functions and constructions of permutation groups ⋮ Isomorphism testing of read-once functions and polynomials ⋮ Symmetry groups of Boolean functions. ⋮ Wreath product in automorphism groups of graphs ⋮ Orbit closed permutation groups, relation groups, and simple groups ⋮ Cut approach to invariance groups of lattice-valued functions ⋮ Almost all Boolean functions have no linear symmetries ⋮ Invariance groups of finite functions and orbit equivalence of permutation groups. ⋮ Regular symmetric groups of Boolean functions. ⋮ Invariance groups of functions and related Galois connections ⋮ Cyclic permutation groups that are automorphism groups of graphs ⋮ Computing the number of affine equivalent classes on \(\mathcal{R}(s,n)/\mathcal{R}(k,n)\) ⋮ Partially Symmetric Functions Are Efficiently Isomorphism Testable

This page was built for publication: Boolean Functions, Invariance Groups, and Parallel Complexity