Representation of direct product of permutation groups as symmetry groups of boolean functions

• Autorzy: Jasionowski P.

Warianty tytułu

PL

Reprezentacja produktu prostego grup permutacji za pomocą grup symetrii funkcji boolowskich

• Języki publikacji: EN

Abstrakty

EN

We consider boolean functions invariance groups S(f) and some special kinds of boolean functions. We construct a k valued boolean function f which represent a direct product of two permutation groups and give an upper bound of k. Moreover we show that in some cases we can construct 2 valued boolean function which represent this product.

PL

Rozważamy moduł M o n stanach wejściowych x1, x2,....... xn, z których każdy może przyjmować jeden z dwóch możliwych stanów 0 lub 1. Ponadto na wyjściu rozważany moduł przyjmuje także tylko te same dwa stany 0 lub 1 (uogólnieniem takich modułów są urządzenia przyjmujące na wyjściu k różnych wartości dla k większe niż 2, o których także piszemy w jednym z rozdziałów tej pracy). Wyjście modułu w ogólności zależy od uporządkowania danych wejściowych x1, x2,....... xn. Istnieja˛ pewne permutacje danych wejściowych które pozostawiają stan wyjściowy niezmieniony. Na przykład jeśli wyjście modułu M w ogóle nie zależy od uporządkowania danych wejściowych to taki moduł nazywamy symetrycznym. Każdy taki moduł może być jednoznacznie powiązany z opisującą go funkcją boolowską. Mając daną taką funkcję możemy skonstruować grupę permutacji (grupę symetrii) odpowiadajacątej funkcji. Dla funkcji boolowskiej f : {0,1}n strzałka w prawo {0,1,....., k-1} grupę taką definiujemy jako zbiór wszystkich permutacji sigma należących do grupy symetrycznej zbioru n elementowego które spełniają warunek f(x1, x2,..... xn) = f(x sigma(1), x sigma (2),.... x sigma(n)) dla dowolnego wektora boolowskiego (x1, x2, …... xn). Punktem wyjścia do naszych rozważań były prace P. Clote, E. Kranakis, Boolean function invariance groups, and parallel complexity., J. Comput., Vol. 20, No. 3, 1991, 553-590. oraz P. Clote, E. Kranakis, Boolean function and Computation Models, Springer, Berlin, 2002. W pracach tych pojawiły się pewne specjalne konstrukcje funkcji boolowskich oraz grup symetrii tych funkcji. Rozważany problem ma bezpośrednie odniesienie do ułożenia takich modułów w układzie scalonym, w którym permutacje danych wejściowych są dozwolone, lub gdy porządek wejść jest zadany tylko częściowo. Główne rezultaty uzyskane w tej pracy dotyczą iloczynów prostych grup permutacji, a w szczególności iloczynów prostych grup symetrycznych. Przedstawiono tu konkretne algorytmy tworzenia funkcji boolowskich w przypadkach gdy rozważamy iloczyny dowolnej (skończonej) liczby grup symetrycznych. Rozważania zostały podzielone na kilka odrębnych przypadków. W sytuacji ogólnej, gdy rozważamy iloczyn prosty dowolnych grup permutacji podajemy ograniczenie górne dla k reprezentowalności poprzez funkcję boolowska. Podobnie jak autorzy P. Clote, E. Kranakis uważamy, że rozważania dotyczące grup symetrii funkcji boolowskich doprowadzą do algorytmów optymalizujących przestrzeń w projektowaniu układów VLSI. W szczególności mogą one odpowiedzieć na pytanie, kiedy możemy zamienić miejscami poszczególne moduły lub bloki modułów nie zmieniając przy tym uzyskiwanej funkcji na wyjściu.

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2012
• Tom: Vol. 24, No. 2
• Strony: 119--133
• Opis fizyczny: Bibliogr. 7 poz., rys.

Twórcy

autor

Jasionowski P.

• Faculty of Applied Mathematics Silesian University of Technology ul. Kaszubska 23, 44-100 Gliwice, Poland,

Bibliografia

• 1. L. Beame, H. Bodlaender: Distributed computing and transitive networks, 6th Annual Symposium of Theoretical Aspects of Computer Science, 1989.
• 2. N.L. Biggs, A.T. White: Permutation groups and combinatorial structures, London Math. Soc., Lecture Notes Series 33, Cambridge Univ. Press. Cambridge, 1979.
• 3. P. Clote, E. Kranakis: Boolean function invariance groups, and parallel complexity, J. Comput., Vol. 20, No. 3, 1991, 553-590.
• 4. P. Clote, E. Kranakis: Boolean function and Computation Models, Springer, Berlin, 2002.
• 5. M. Grech, A. Kisielewicz: Direct product of automorphism groups of colored graphs, Discrete Math., 283, 2004, 81-86.
• 6. M. Harrison: On the classification of Boolean functions by the general linear and affine groups, J. Soc. Indust. Apply Math, 12, 1964, 285-299.
• 7.A. Kisielewicz: Symmetry groups of Boolean functions and constructions of permutation groups, Journal of Algebra., 199 , 1998, 379-403.