O rozwiązaniach i niektórych zastosowaniach liniowych ograniczeń w zbiorze {0, 1}

• Autorzy: Kryvyy S. , Grzywacz W. , Łopatina M. W.

Warianty tytułu

EN

About solutions and specific utilizations of linear constraints over set of {0, 1}

• Języki publikacji: PL

Abstrakty

PL

Liniowe ograniczenia odgrywają ważną rolę w wiciu dziedzinach współczesnej nauki obliczeniowej dzięki temu. że wiele problemów z tych dziedzin redukuje się do rozwiązania tych liniowych ograniczeń lub sprawdzenia spełnialności w zbiorze liczb całkowitych lub naturalnych. Takie ograniczenia i systemy ograniczeń nazywamy diofantycznymi. Szczególnym przykładem systemów liniowych ograniczeń diofantycznych są systemy jednorodnych, liniowych równań w zbiorze {0, 1}. Oznacza to, że współczynniki tych układów równań są liczbami ze zbioru {-1, 0,1} a rozwiązania szuka się w zbiorze {0, 1}. W artykule zostaną, zaproponowane metody rozwiązań zarówno w przypadku jednego równania, jak i układu równań.

EN

Linear constraints play great role in computer science. because very many problems are reduced to solutions of such systems of contraints over set of natural numbers or over set {0, 1}. These constraints are called the Diophantine linear consiraints. In this paper are consider some methods of solutions and some applications of solution algorithms.

Słowa kluczowe

PL

system diofantyczny; ograniczenia liniowe; ograniczenia diofantyczne

EN

diophantine system; linear constraints; diophantine constraints

• Wydawca: Oficyna Wydawnicza Politechniki Rzeszowskiej
• Czasopismo: Zeszyty Naukowe Politechniki Rzeszowskiej. Informatyka
• Rocznik: 2003
• Tom: z. 2 [206]
• Strony: 43--55
• Opis fizyczny: Bibliogr. 9 poz., rys., tab.

Twórcy

autor

Kryvyy S.

autor

Grzywacz W.

autor

Łopatina M. W.

• Politechnika Rzeszowska

Bibliografia

• [1] Murata T.: Petri Nets: Properties, Analysis and Applications. Proceeding of the IEEE, vol. 77, no 4, 1989, 541-580.
• [2] Baader F., Ziekmann J.: Unification theory. Handbook of Logic in Artificial Intelligence and Logic Programming. Oxford University Press, 1994, 1-85.
• [3] Zajcew D.A.: Diekompozicyja sietiej Petri. Kibiernietika i sistiemnyj analiz. Naukowa dumka, 2002, 113-123.
• [4] Comon H.: Constraint solving on terms: Automata techniques (Preliminary lecture notes). Intern. Summer School on Constraints in Computational Logics, Gif-sur-Yvette, France 1999, 22.
• [5] Clausen M., Fortenbacher A.: Efficient solution of linear diophantine equations. Journ. Symbolic Computation, vol. 8, no 1,2, 1989, 201-216.
• [6] Domenjoud E.: Outils pour la deduction automatique dans les theories associatives -commutatives. Thesis de Doctorat d'Universite: Universite de Nancy, 1991.
• [7] Krivoi S.: Criteria of Satisfiability for Homogeneous Systems of Linear Diophantine Constraints. Lee. Not. in Comp. Sci., no 2328, 2002, 264-271.
• [8] Usatjuk O.B.: O riealizacyi inkriemientalnoj wiersii algoritma prowierki sowmiestnosti sistiem liniejnych diofantowych urawnienij w oblasti naturalnych czisiel. Uprawlajuszczije sistiemy i maszyny, no 3, 2002, 26-32.
• [9] Contenjean E., Devie H.: An efficient algorithm for solving systems of diophantine equations. Inform. Comput., 113, vol.1, 1994, 143-172.