Fundamenta Informaticae - Volume 188, issue 1

Authors: Bagheri Gh., Behrooz | Feder, Tomas | Fleischner, Herbert | Subi, Carlos

Article Type: Research Article

Abstract: In this paper we deal with hamiltonicity in planar cubic graphs G having a facial 2–factor 𝒬 via (quasi) spanning trees of faces in G /𝒬 and study the algorithmic complexity of finding such (quasi) spanning trees of faces. Moreover, we show that if Barnette’s Conjecture is false, then hamiltonicity in 3–connected planar cubic bipartite graphs is an NP-complete problem.

Keywords: Barnette’s Conjecture, eulerian plane graph, hamiltonian cycle, spanning tree of faces, A–trail

DOI: 10.3233/FI-222139

Citation: Fundamenta Informaticae, vol. 188, no. 1, pp. 1-14, 2022

Authors: Bès, Alexis | Choffrut, Christian

Article Type: Research Article

Abstract: Given a subset of X ⊆ ℝn we can associate with every point x ∈ ℝn a vector space V of maximal dimension with the property that for some ball centered at x , the subset X coincides inside the ball with a union of lines parallel to V . A point is singular if V has dimension 0. In an earlier paper we proved that a 〈ℝ, +, <, ℤ〉-definable relation X is 〈ℝ, +, <, 1〉-definable if and only if the number of singular points is finite …and every rational section of X is 〈R, +, <, 1〉-definable, where a rational section is a set obtained from X by fixing some component to a rational value. Here we show that we can dispense with the hypothesis of X being 〈ℝ, +, <, ℤ〉-definable by requiring that the components of the singular points be rational numbers. This provides a topological characterization of first-order definability in the structure 〈ℝ, +, <, 1〉. It also allows us to deliver a self-definable criterion (in Muchnik’s terminology) of 〈ℝ, +, <, 1〉- and 〈ℝ, +, <,ℤ〉-definability for a wide class of relations, which turns into an effective criterion provided that the corresponding theory is decidable. In particular these results apply to the class of so-called k –recognizable relations which are defined by finite Muller automata via the representation of the reals in a integer basis k , and allow us to prove that it is decidable whether a k –recognizable relation (of any arity) is l –recognizable for every base l ≥ 2. Show more

DOI: 10.3233/FI-222140

Citation: Fundamenta Informaticae, vol. 188, no. 1, pp. 15-39, 2022

Authors: Mrozek, Ireneusz | Shevchenko, Nikolai A. | Yarmolik, Vyacheslav N.

Article Type: Research Article

Abstract: This paper presents the universal address sequence generator (UASG) for memory built-in-self-test. The studies are based on the proposed universal method for generating address sequences with the desired properties for multirun march memory tests. As a mathematical model, a modification of the recursive relation for quasi-random sequence generation is used. For this model, a structural diagram of the hardware implementation is given, of which the basis is a storage device for storing so-called direction numbers of the generation matrix. The form of the generation matrix determines the basic properties of the generated address sequences. The proposed UASG generates a wide …spectrum of different address sequences, including the standard ones, such as linear, address complement, gray code, worst-case gate delay, 2i , next address, and pseudorandom. Examples of the use of the proposed methods are considered. The result of the practical implementation of the UASG is presented, and the main characteristics are evaluated. Show more

Keywords: antirandom tests, controlled random tests, multiple tests, RAM testing

DOI: 10.3233/FI-222141

Citation: Fundamenta Informaticae, vol. 188, no. 1, pp. 41-61, 2022