Menu: Home :: go to Journal :: switch to Russian :: switch to English
You are here: all Journals and Issues→ Journal→ Issue→ Article

Modeling of combinatorial problems with the help of continuous logic

Annotation

In this paper we formulated the class of combinatorial tasks, which equivalent to problem of determining the relative position of slot sequences. We propose examples of this class of problems related to the field of synthesis of reliable devices by redundancy, organization management of customer service in trading systems, drafting proper timetable of dissertation council. We give precise mathematical formulation of problem, consisting of the analysis part (determining the actual position of interval sequences) and synthesis (finding location conditions for interval sequences at which their relative positions form a desired order). The mathematical model of dynamic finite automaton without memory as a logical -pole is introduced. The main task for this automaton is to find the output dynamic process by known input processes and implemented logical (Boolean) function. Detailed description of continuous logic as mathematical means that allow find the output dynamic process in automata is given. Examples of such a finding are presented. It is shown that the dynamic finite automaton without memory is adequate mathematical model to solve the combinatorial problem. At the same time the original combinatorial problem reduces to finding the output process in the automata model, based on the specified input processes and implemented logic function. An 6-step algorithm for solving the problem, as well as two examples of combinatorial problems that are solved by this algorithm are proposed. Both examples are solved in analytical form. We release the estimation of computational complexity which implies that the complexity of the proposed approach is growing as a power function of the dimension of the problem. So the approach is applicable to the solution of problems of high dimensionality. The advantage of the approach else in the ability to formally seek algorithms for solving problems and analyze probable solutions by finding the necessary and sufficient conditions for existence of such solutions.

Keywords

combinatorial problem; sequence of intervals; intervals interposition; the dynamic automata; the dynamic process; the continuous logic

Full-text in one file

Download

DOI

10.20310/1810-0198-2017-22-2-439-448

UDC

519.715

Pages

439-448

References

1. Levin V.I. Vvedenie v dinamicheskuyu teoriyu konechnykh avtomatov [Introduction to Dynamic Theory of Finite State Automation]. Riga, Zinatne Publ., 1975. (In Russian). 2. Bochmann D., Roginskij V.N., Levin V.I. Dinamische Processe in Automaten. Berlin, Technik Publ., 1977. (In German). 3. Levin V.I. Dinamika logicheskikh ustroystv i system [Dynamics of Logical Devices and Systems]. Moscow, Energy Publ., 1980. (In Russian). 4. Levin V.I. Teoriya dinamicheskikh avtomatov [Theory of Dynamic Automation]. Penza, Penza State University Publ., 1995. (In Russian). 5. Levin V.I. Beskonechnoznachnayalogika v zadachakh kibernetiki [Infinite-Valued Logics in Cybernetics Tasks]. Moscow, Radio i svyaz' Publ., 1982. (In Russian). 6. Levin V.I. Strukturno-logicheskie metody issledovaniy aslozhnykh system [Structural-Logical Methods of Complicated Systems Research]. Moscow, Nauka Publ., 1987. (In Russian). 7. Zade L. Ponyatie lingvisticheskoy peremennoy i ego primenenie k prinyatiyu priblizhennykh resheniy [The Notion of Linguistic Variable and its Application to Taking Approximate Solutions]. Moscow, Mir Publ., 1976. (In Russian). 8. Kandrashina E.Yu., Litvintseva L.V., Pospelov D.A. Prostranstvo i vremya v sistemakh iskusstvennogo intellekta [The Space and Time in Artificial Intellect Systems]. Moscow, Nauka Publ., 1988. (In Russian). 9. Kandrashina E.Yu., Litvintseva L.V., Pospelov D.A. Predstavlenie znaniy o prostranstve i vremeni v sistemakh iskusstvennogo intellekta [The Space and Time Notion Inartificial Intellect Systems]. Moscow, Nauka Publ., 1989. (In Russian).

Received

2016-05-17

Section of issue

Physical and mathematical sciences

Для корректной работы сайта используйте один из современных браузеров. Например, Firefox 55, Chrome 60 или более новые.