Wyniki wyszukiwania - BazTech

1

On Minimization and Learning of Deterministic ω-Automata in the Presence of Don't Care Words

Löding Christof, Stachon Max Philip

Fundamenta Informaticae

|

2022

|

Vol. 189, nr 1.

69--90

EN

We study minimization problems for deterministic ω-automata in the presence of don't care words. We prove that the number of priorities in deterministic parity automata can be efficiently minimized under an arbitrary set of don't care words. We derive that from a more general result from which one also obtains an efficient minimization algorithm for deterministic parity automata with informative right-congruence (without don't care words). We then analyze languages of don't care words with a trivial right-congruence. For such sets of don't care words it is known that weak deterministic Büchi automata (WDBA) have a unique minimal automaton that can be efficiently computed from a given WDBA (Eisinger, Klaedtke 2006). We give a congruence-based characterization of the corresponding minimal WDBA, and show that the don't care minimization results for WDBA do not extend to deterministic ω-automata with informative right-congruence: for this class there is no unique minimal automaton for a given don't care set with trivial right congruence, and the minimization problem is NP-hard. Finally, we extend an active learning algorithm for WDBA (Maler, Pnueli 1995) to the setting with an additional set of don't care words with trivial right-congruence.

2

Relationship between basic physiochemical properties of seawater and magnitude of underwater electric field

Narożny M., Polański P., Namiotko R., Czarnowska M.

Zeszyty Naukowe Akademii Marynarki Wojennej

|

2018

|

R. 59 nr 4 (215)

63--75

EN

Passive defense systems which minimize chance of vessel detection have to be utilized due to application of naval mines. Passive defense and signature minimization can be regarded as not only magnitude reduction but also as its shaping. Electric field magnitude at a given depth is a function of an electric field source but also it depends on physicochemical properties of seawater — temperature and salinity. In this paper results of underwater electric field simulations are presented. Cases of various depths, temperatures and salinities are shown. Computational results are compared to underwater electric field measurements performed with portable sensor.

PL

Zagrożenia wynikające ze stosowania min morskich wymuszają użycie na okrętach systemów minimalizujących prawdopodobieństwo ich wykrycia — obronę bierną. Minimalizacja pól fizycznych oznacza zmniejszenie maksymalnego natężenia pola oraz jego kształtowanie. Natężenie pola elektrycznego na zadanej głębokości pomiarowej jest zależne nie tylko od parametrów źródła, ale również od właściwości fizykochemicznych wody — jej temperatury oraz zasolenia. W artykule przedstawiono wyniki symulacji komputerowych natężenia pola elektrycznego na różnych głębokościach i w kilku wybranych środowiskach charakteryzujących się różnymi wartościami temperatury oraz zasolenia. Wyniki symulacji zestawiono z wartościami natężenia pola elektrycznego zmierzonego przez przenośny układ pomiarowy.

3

Speed Targeted Minimization of Finite State Machines for CPLDs

Klimowicz A.

Measurement Automation Monitoring

|

2018

|

Vol. 64, No. 1

5--7

EN

A method of the minimization finite state machines (FSM) is proposed. In this method, such optimization criterion as the critical delay path is taken into account already at the stage of minimizing internal states. The method is based on sequential merging of two internal states including the optimization criteria. The critical path is estimated for CPLD devices. In addition, the proposed method allows one to minimize the number of transitions and input variables of the FSM. Experimental results shows, that the maximum clock frequency of minimized FSMs is higher by 17% comparing to initial FSM.

4

On Transformation of a Logical Circuit to a Circuit with NAND and NOR Gates Only

Baranov S., Karatkevich A.

International Journal of Electronics and Telecommunications

|

2018

|

Vol. 64, No. 3

373--378

EN

In the paper we consider fast transformation of a multilevel and multioutput circuit with AND, OR and NOT gates into a functionally equivalent circuit with NAND and NOR gates. The task can be solved by replacing AND and OR gates by NAND or NOR gates, which requires in some cases introducing the additional inverters or splitting the gates. In the paper the quick approximation algorithms of the circuit transformation are proposed, minimizing number of the inverters. The presented algorithms allow transformation of any multilevel circuit into a circuit being a combination of NOR gates, NAND gates or both types of universal gates.

5

On a fair manifold fare rating on a long traffic line

Palúch S., Majer T.

Transport Problems

|

2017

|

T. 12, z. 2

5--11

EN

The paper studies the possibilities to design a fair manifold tariff on a long traffic line. If a single tariff is used on a long bus or railway line, passengers travelling long distances are favoured at the expense of those travelling short distances. The fairest approach to tariff is setting an individual tariff for every origin–destination relation of line stops that expresses real travel costs. However, sometimes the individual tariff is too complicated and is therefore replaced by double-, triple- or manifold tariff. This paper shows how to design a manifold tariff in order to minimize unfairness to passengers.

6

Minimization of finite state machines by states merging

Salauyou V.

Measurement Automation Monitoring

|

2016

|

Vol. 62, No. 5

179--181

EN

The paper presents a method for minimization of finite state machines (FSMs) with unspecified values of output variables. The proposed method is based on merging of two states. In addition to reduction of the FSM states, the method also allows reducing the number of FSM transitions and FSM input variables. This method enables reducing the number of internal states of the initial FSM by 1.22 times on the average, and by 2.75 times on occasion. An average reduction of the number of FSM transitions makes up 1.32 times, and on occasion may amount to 2.27 times. The comparison of the method with the program STAMINA shows that the offered method allows decreasing the number of FSM transitions by 1.55 times on the average, and by 3.92 times on occasion.

7

Metody sprzężeń czasowych w inżynierii przedsięwzięć budowlanych

Bożejko W., Hejducki Z., Rogalska M., Wodecki M.

Materiały Budowlane

|

2016

|

nr 6

11--12

PL

Celem artykułu było wskazanie kierunków badawczych w inżynierii przedsięwzięć budowlanych z zastosowaniem metod sprzężeń czasowych. Problem badawczy dotyczy optymalizacji cyklu realizacji przedsięwzięć budowlanych, w szczególności poszukiwania metod obliczeniowych uwzględniających ograniczenia technologiczne i organizacyjne w systemach pracy potokowej (flow shop problem). Jako kryteria optymalizacyjne przyjęto minimalizację czasu, kosztów i zasobów oraz inne funkcje celu.

EN

The aim of the article was to point out directions in research about methodology of scheduling construction project management when is applied time couplings method. Science problem is to optimization cycle of construction process, especially to study calculation method using technology and organization restrictions in flow shop problem. Criteria of the optimization were to minimization time, costs and resources and other.

8

Minimization and Characterizations for Biautomata

Holzer M., Jakobi S.

Fundamenta Informaticae

|

2015

|

Vol. 136, nr 1/2

113--137

EN

We show how to minimize biautomata with adaptations of classical minimization algorithms for ordinary deterministic finite automata and moreover by a Brzozowski-like minimization algorithm by applying reversal and power-set construction twice to the biautomaton under consideration. Biautomata were recently introduced in [O. KL´I MA, L. POL´A K: On biautomata. RAIRO— Theor. Inf. Appl., 46(4), 2012] as a generalization of ordinary finite automata, reading the input from both sides. The correctness of the Brzozowski-like minimization algorithm needs a little bit more argumentation than for ordinary finite automata since for a biautomaton its dual or reverse automaton, built by reversing all transitions, does not necessarily accept the reversal of the original language. To this end we first use the recently introduced notion of nondeterminism for biautomata [M. HOLZER, S. JAKOBI: Nondeterministic Biautomata and Their Descriptional Complexity. In: 15th DCFS, Number 8031 of LNCS, 2013] and take structural properties of the forward- and backward-transitions of the automaton into account. This results in a variety of biautomata models, the accepting power of which is characterized. As a byproduct we give a simple structural characterization of cyclic regular and commutative regular languages in terms of deterministic biautomata.

9

Koszt implementacji w strukturach CPLD i FPGA jako kryterium wyboru stanów przy minimalizacji automatu skończonego

Klimowicz A.

Pomiary Automatyka Kontrola

|

2014

|

R. 60, nr 7

480--482

PL

W pracy opisano heurystyczną metodę minimalizacji automatów skończonych, która pozwala na etapie minimalizacji stanów uwzględniać parametry bazy technologicznej oraz metodę kodowania stanów. Opisano kryteria minimalizacji liczby stanów ze względu na koszt ich realizacji w strukturze CPLD, gdzie głównym parametrem wpływającym na realizację jest liczba termów podłączonych do jednej makrokomórki i liczba elementarnych koniunkcji w opisie SOP (Sum of Products) funkcji logicznej oraz FPGA, gdzie głównym parametrem jest liczba wejść elementu logicznego i liczba argumentów realizowanej funkcji logicznej. Przedstawiono także wyniki badań opracowanych algorytmów i porównanie ich z innymi metodami minimalizacji stanów.

EN

In the paper a heuristic method of minimization of incompletely specified finite state machines is described. This method allows taking into account the parameters of technological base, the method of state assignment and realization costs. The presented method is focused on realization of FSM in CPLD and FPGA structures. The method is based on operation of merging two states. In addition to reducing internal states this method minimizes the number of FSM transitions and FSM input variables. In contrast to the previously developed methods, in each step of the algorithm there is considered not only one, but the entire set of all pairs of states for which it is permissible to merge. Then from the set there is selected the pair of states which best matches the criteria of minimizing. The paper describes the criteria for minimizing the number of states of the machine because of the cost of their implementation in the CPLD. The main parameter influencing the implementation is a number of terms connected to one macrocell and FPGA structures, where the main parameter is the number of LUT inputs and the number of logic function arguments. The results of implementation of the minimized FSMs in programmable devices showed that the proposed method allowed building FSMs at lower cost and higher speed than STAMINA program for CPLD and FPGA devices.

10

On the Transition Reduction Problem for Finite Automata

Dahmoune M., Abdalaoui E. H., Ziadi D.

Fundamenta Informaticae

|

2014

|

Vol. 132, nr 1

79--94

EN

In this paper we apply the concept of common follow sets (CFS) of a regular expression to homogeneous finite state automaton. Based on this concept and using particular binary trees, we devise an efficient algorithm to reduce (minimize) the number of transitions of the automaton recognizing the language L(En) denoted by the regular expression En= (1 + ε) · (2 + ε) · (3 + ε) · · · (n+ε). Experiments reveal that for small values of n, all ε –free NFAs with n+1 states and with a minimum number of transitions for L(En) are exactly those obtained by our construction. Also, the produced ε-free NFA is asymptotically minimal, in the sense that the number of transitions is equivalent to n(log2 n)2 which corresponds in the same time to the upper and the lower bound. We conjecture that our construction is not only a reduction but a minimization for L(En).

11

Metoda minimalizacji momentu zaczepowego w wielobiegunowych maszynach z magnesami trwałymi

Goryca Z.

Wiadomości Elektrotechniczne

|

2013

|

R. 81, nr 12

22--23

PL

Przedstawiono nowy sposób minimalizacji momentu zaczepowego i nową konstrukcję wielobiegunowej maszyny o niskim momencie zaczepowym.

EN

The paper presents a new method for minimization of cogging torque and a new design of multipolar machine with low cogging torque.

12

Minimization of bus stop number on a bus station

Palúch S.

Transport Problems

|

2013

|

T. 8, z. 1

113--118

EN

A bus station contains several bus stops. Only one bus can occupy a single bus stop at a time. Buses of many trips arrive to the bus station during the day (or during another considered period) and every bus occupies a bus stop for a certain time interval. The set of available bus stops is limited. This paper studies a problem how to assign a bus stop to every bus trip in order to minimize the number of assigned bus stops and in order to comply several additional conditions. Several approaches to this problem are presented. These approaches differ according to considered additional conditions.

PL

Na stacji autobusowej może znajdować się kilka platform. W tym samym czasie przy jednej platformie może znajdować się tylko jeden autobus. W ciągu dnia na stację autobusową przyjeżdżają autobusy z różnych połączeń i każdy z nich zajmuje platformę przez określony czas. Ten artykuł ma na celu pokazanie problemu przyporządkowania platform do wszystkich połączeń i jednoczesnej minimalizacji liczby platform przy spełnieniu określonych warunków. Prezentowane są różne sposoby rozwiązania problemu. Każdy ze sposobów różni się w zależności od dalszych warunków.

13

Minimalizacja automatów skończonych z uwzględnieniem ich kosztu realizacji w układach programowalnych o strukturze CPLD

Klimowicz A.

Pomiary Automatyka Kontrola

|

2013

|

R. 59, nr 8

760--762

PL

W pracy opisano heurystyczną metodę minimalizacji nie w pełni określonych automatów skończonych, która pozwala już na etapie minimalizacji stanów wewnętrznych uwzględniać parametry bazy technologicznej, metodę kodowania stanów oraz optymalizować koszt realizacji automatu w strukturze programowalnej. Opisano kryteria minimalizacji liczby stanów automatu ze względu na koszt ich realizacji w strukturze CPLD, gdzie głównym parametrem wpływającym na realizację jest liczba termów podłączonych do makrokomórki. Dodatkowym efektem działania metody jest minimalizacja liczby przejść automatu.

EN

In the paper a heuristic method of minimization of incompletely specified finite state machines is described. This method allows taking into account parameters of technological base, the method of state assignment and realization costs. The presented method is focused on realization of an FSM in the CPLD structure. The method is based on an operation of merging two states. In addition to reducing internal states, this method minimizes the number of FSM transitions and FSM input variables. In contrast to the previously developed methods, in each step of the algorithm there is considered not only one, but the entire set of all pairs of states for which it is permissible to merge. Then the pair of states which best matches the criteria of minimizing is selected from the set. Two FSM states can be merged if they are equivalent. FSM behavior does not change after the states are merged, if the transition conditions from these states that lead to different states are orthogonal. If there are transi-tions from the states that lead to the same states, the transition conditions for such transitions should be equal. Moreover, the output vectors generated in these states should not be orthogonal. It should be noted that wait states can be formed at the merging of FSM states. This paper describes the criteria for minimizing the number of states of the machine because of the cost of their implementation in the CPLD structure, where the main parameter influencing the implementation is a number of terms connected to one macrocell.

14

Wpływ wodoru na sterowanie zużyciem paliwa w procesie wielkopiecowym

Bernasowski M.

Hutnik, Wiadomości Hutnicze

|

2013

|

Vol. 80, nr 11

756--760

PL

W artykule przedstawiono analizę wpływu różnych zawartości wodoru i tlenku węgla na równowagę procesów redukcji w warunkach odpo- wiadających wielkiemu piecu. Obliczenia przeprowadzono za pomocą termochemicznego oprogramowania i baz danych FactSage. Przedstawiono również mechanizm wpływu zwiększonego udziału wodoru w gazie garowym na konstrukcję modelu minimalizacji zużycia paliwa.

EN

The presented paper shows analysis of the hydrogen and carbon monoxide influence on the equilibrium of iron oxides reduction at conditions corresponded with the blast furnace process. The calculations were performed by using the FactSage thermochemical software and databases. There is also presented the mechanism of the increased hydrogen share at the bosh gas impact on the construction of the fuel rate minimization model.

15

Minimization of torque ripples in BLDC motors due to phase commutation - a review

Salah W. A., Ishak D., Hammadi K. J.

Przegląd Elektrotechniczny

|

2011

|

R. 87, nr 1

183-188

EN

The smoothness of variable speed drive operation is critical and a viable measure used in the design and development of motion control applications. The torque produced in a brushless DC (BLDC) motor with trapezoidal back electromotive force (BEMF) is constant under ideal conditions. However, in practice, torque ripple appears on the delivered output torque. Some of these ripples result from the natural structure of the motor, while some are related to the motor design parameters. Nevertheless, these torques could be minimized throughout the machine design process. Another source of ripples is associated with the control and drive side of the motor. This paper focuses on the torque ripples associated with machine control and drives that could be minimized by applying different control techniques. Various applied techniques for minimizing the torque ripples in BLDC are presented based on the motor control side. There are a variety of configurations to be adjusted based on the applied technique; in addition, hardware modifications or additional stages are also required. Other techniques, such as algorithm-based ones, could be applied to standard motor drive configurations.

PL

Płynność zmian szybkości napędu jest istotną miarą używaną w projektowaniu i rozwoju zastosowań kontroli ruchu. Moment wytwarzany przez bezszczotkowy silnik DC z trapezoidalną zwrotną siłą elektromotoryczną jest stały w warunkach idealnych. Jednak w praktyce pojawiają się zafalowania momentu. Niektóre z tych zafalowań wynikają z naturalnej konstrukcji silnika, ale inną są związane z parametrami projektu i mogą być zmniejszane przez właściwe projektowanie. Inne zafalowania są związane z układem sterowania. Ten artykuł koncentruje się na zafalowaniach wynikających z techniki sterowania. Przedstawiono różne możliwości zmniejszania zafalowań.

16

Variational analysis of one-dimensional nonconvex Neumann problem

Puchała P.

Prace Naukowe Instytutu Matematyki i Informatyki Politechniki Częstochowskiej

|

2011

|

Vol. 10, nr 1

215-221

EN

We consider a variational formulation of a nonconvex one-dimensional Neumann problem. The method of obtaining infimum of a relevant functional is based on a general theorem attributed to Z. Naniewicz, of the minimization of a certain class of nonconvex functionals.

17

Compact Representations and Efficient Algorithms for Operating Guidelines

Lohmann N., Wolf K.

Fundamenta Informaticae

|

2011

|

Vol. 108, nr 1/2

43-62

EN

Operating guidelines characterize correct interaction (e. g., deadlock freedom) with a service. They can be stored in a service registry. They are typically represented as an annotated transition system where the annotations are Boolean formulae attached to the states. The core result of this article is to propose an alternative representation of operating guidelines where, instead of a Boolean formula, only a few bits need to be stored with a state. This way, we safe one order of magnitude in the space complexity of the representation. Moreover, we demonstrate that the new representation yields efficiency gains in several algorithms which involve operating guidelines. Finally we show that the new representation permits the translation of the transition system representing the operating guidelines into a Petri net which typically yields further gains concerning the space for storing operating guidelines.

18

Minimalizacja strumienia materiałowego przez racjonalne rozmieszczenie modułów technologicznych w gniazdach produkcyjnych

Gorski S.

Zeszyty Naukowe Politechniki Rzeszowskiej. Mechanika

|

2009

|

z. 76 [261]

53-58

EN

There is a description of the question of a decrease in costs for transportation of products in machine-assembling production in this article. This decrease is based on the procedure, which is offered by the author and is founded on optimization of material flows on a production section due to a rational arrangement of the technological modules on it. The developed procedure of construction of schemes of an arrangement of the manufacturing equipment on production sections can be used not only at designing of cell-type systems, but also at their operation due to rearrangement machines under conditions of changing of listed products, providing thus a planning flexibility of production.

19

Analiza procesu stacjonarnego przepływu ciepła na podstawie zasady minimalizacji generowania entropii

Hołda A.

Rudy i Metale Nieżelazne

|

2008

|

R. 53, nr 5

275-281

PL

W artykule porównano dwa przypadki przewodzenia ciepła w izolacji termicznej, problem klasyczny oraz minimalizujący generację entropii. Jako kryterium porównawcze wybrano wielkość ciepła odpadowego. Pokazano wpływ minimalizacji źródeł entropii przy przewodzeniu ciepła na bilans energetyczny procesu technologicznego. Rozważania poparto przykładami obniżającymi źródła entropii w izolacji.

EN

Comparison of the solution of two different boundary-value problems of heat conduction in solid isolation has been presented. The solution of the classical formulation of steady state problem and solution based on the entropy generation minimization principle are analyzed. Waste heat flow to surrounding has been chosen as the comparison criterion. Influence of the minimization of entropy generation an the energy balance and thermodynamic efficiency of the technological process has been shown. Theoretical considerations have been illustrated with numerical example.

20

Wykorzystanie komputerowego wnioskowania w projektowaniu kombinacyjnych układów sterowania

Tkacz J., Adamski M.

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2008

|

R. 81, nr 6

728-730

PL

Przedstawiono możliwości zastosowania komputerowego wnioskowania symbolicznego Gentzena w projektowaniu układów cyfrowych oraz do rozwiązywania skomplikowanych problemów logicznych. Wykorzystując przykład sterownika zaczerpnięty z literatury, przedstawiono sposób uzyskiwania uproszczonego opisu układu kombinacyjnego, kilkukrotnie odwołujący się do systemu wnioskującego. Metoda polega na zastąpieniu silnie nieokreślonej klasycznej tablicy decyzyjnej sekwentami, które opisują relacje pomiędzy wejściami i wyjściami układu. W wyniku normalizacji tych sekwentów otrzymuje się zbiór reguł typu if-then, równoważny formie koniunkcyjnej lub dysjunkcyjnej funkcji boolowskich.

EN

The paper presents a new idea of an application of Gentzen logic symbolic reasoning for solving some combinational problems in the digital system design. Taking into account an example of industrial combinational logic controller, which could be alternatively described in classic way as an binary decision table, it is demonstrated how to apply a new efficient version of automated theorem prover in propositional sequent logic for a direct design from behavioural specification.