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

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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