The equivalence problem of multidimensional multitape automata

This article considers the equivalence problem of multitape automata with multidimensional tapes, where the motion of the heads is monotone in all directions (no backward motion). It is shown that this problem can be reduced to the equivalence problem of ordinary multitape automata. Some applications of the result are adduced.     

Asynchronous trace-matching automata

This paper presents algorithms for solving several matching problems on Mazurkiewicz traces. The creation of the algorithms is reduced to the construction of automata that recognize corresponding rational trace languages. Such languages and their properties were studied by many authors. This paper considers trace languages used in solving concrete problems that have analogs in stringology.     

Equivalence of regular expressions over a partially commutative alphabet

The equivalence problem is considered for regular expressions over a partially commutative alphabet. The alphabet is decomposed into disjoint subsets of noncommutative elements. The special case of the problem when the cardinal number of only one subset is larger than 1 and the cardinal numbers of the other subsets are equal to 1 is proved to be algorithmically solvable. Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 65–74, May–June 2009.     

Symmetry Measure for Memory Test and Its Application in BIST Optimization

Programmable Built-in Self-Test (BIST) has been widely used for testing embedded memories. The main disadvantage of having programmability on BIST circuits is the size of Test Algorithm Register (TAR) that becomes very crucial in case of complex test algorithms. To optimize Programmable BIST hardware symmetric March tests are usually used in BIST engines. On the other hand, the used definitions do not reflect completely the existing symmetry in test algorithms and they also do not reflect the fact that the level of symmetry in a given test algorithm can be measured. A new method of symmetry measurement for memory test algorithms and a corresponding metric are introduced. A dependency between symmetry measure and BIST optimization range is analyzed. Optimization experiments that have been done for a number of well-known test algorithms show that the BIST hardware gain could reach 48%. However, the time overhead is negligible in comparison with the hardware gain. The experiments also show that starting from some point a monotone dependency between symmetry measure and BIST hardware area exists.     

Forbidden traces and forbidden subtraces

The concepts of forbidden strings and forbidden subsequences are generalized to traces. This paper presents algorithms for constructing sets of minimal forbidden traces and minimal forbidden subtraces for a given trace.     

Embedded-memory test and repair: infrastructure IP for SoC yield

Today's complex SoCs need sophisticated infrastructure IP, not only to test and diagnose embedded memories but also to repair them and improve fabrication yield. The authors solution integrates memory IP with test and repair IP in a composite infrastructure IP that ensures manufacturing and field repair efficiency and optimizes SoC yield.     

On trace inclusion optimization problems

The following four optimization problems over a finite set of traces are considered: (i) find the longest trace that is included in each trace from a given finite set T of traces, (ii) find the shortest trace that is not included in every trace from a given finite set T of traces, (iii) find the shortest trace that includes every trace from a given finite set T of traces, (iv) find the longest trace that does not include each trace from a given finite set T of traces.     

Inclusion problems in trace monoids

Efficient pattern matching algorithms for traces and their dependence graphs are proposed. Pattern matching problems related to problems of recognizing frequent patterns in structured data and counting the number of trace object windows that include a pattern are considered.