Modeling of combinatorial problems with the help of continuous logic

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.

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