Fundamenta Informaticae - Volume 176, issue 2

Authors: Cheng, Baolei | Fan, Jianxi | Lyu, Qiang | Lin, Cheng-Kuan | Li, Xiaoyan | Chen, Guo

Article Type: Research Article

Abstract: For a network, edge/node-independent spanning trees (ISTs) can not only tolerate faulty edges/nodes, but also be used to distribute secure messages. As important node-symmetric variants of the hypercubes, the augmented cubes have received much attention from researchers. The n-dimensional augmented cube AQn is both (2n ‒ 1)-edge-connected and (2n ‒ 1)-nodeconnected (n ≢ 3), thus the well-known edge conjecture and node conjecture of ISTs are both interesting questions in AQn . So far, the edge conjecture on augmented cubes was proved to be true. However, the node conjecture on AQn is still …open. In this paper, we further study the construction principle of the node-ISTs by using the double neighbors of every node in the higher dimension. We prove the existence of 2k − 1 node-ISTs rooted at node 0 in A Q n ( 00...0 ︸ n − k ) ( n ≥ k ≥ 4 ) by proposing an ingenious way of construction and propose a corresponding O (N logN ) time algorithm, where N = 2k is the number of nodes in A Q n ( 00...0 ︸ n − k ) . Show more

Keywords: Augmented cubes, node-independent spanning trees, constructive algorithm, secure message distribution

DOI: 10.3233/FI-2020-1965

Citation: Fundamenta Informaticae, vol. 176, no. 2, pp. 103-128, 2020

Authors: Kopczyński, Eryk

Article Type: Research Article

Abstract: We construct a first-order formula φ such that all finite models of φ are non-narrow rectangular grids without using any binary relations other than the grid neighborship relations. As a corollary, we prove that a set A ⊆ ℕ is a spectrum of a formula which has only planar models if numbers n ∈ A can be recognized by a non-deterministic Turing machine (or a one-dimensional cellular automaton) in time t (n ) and space s (n ), where t (n )s (n ) ≤ n and t (n ); s (n ) = …Ω(log(n )). Show more

Keywords: spectrum problem, planar graphs, rectangular grids, descriptive complexity, finite model theory

DOI: 10.3233/FI-2020-1966

Citation: Fundamenta Informaticae, vol. 176, no. 2, pp. 129-138, 2020

Authors: Ghosh, Kuntal | Mitra, Sushmita

Article Type: Other

DOI: 10.3233/FI-2020-1967

Citation: Fundamenta Informaticae, vol. 176, no. 2, pp. 139-140, 2020

Authors: Dasgupta, Abhijit | Nayak, Losiana | Das, Ritankar | Basu, Debasis | Chandra, Preetam | De, Rajat K.

Article Type: Research Article

Abstract: Epilepsy is a neurological condition of human being, mostly treated based on the patients’ seizure symptoms, often recorded over multiple visits to a health-care facility. The lengthy time-consuming process of obtaining multiple recordings creates an obstacle in detecting epileptic patients in real time. An epileptic signature validated over EEG data of multiple similar kinds of epilepsy cases will haste the decision-making process of clinicians. In this paper, we have identified EEG data derived signatures for differentiating epileptic patients from normal individuals. Here we define the signatures with the help of various machine learning techniques, viz., feature selection and classification, pattern …mining, and fuzzy rule mining. These signatures will add confidence to the decision-making process for detecting epileptic patients. Moreover, we define separate signatures by incorporating few demographic features like gender and age. Such signatures may aid the clinicians with the generalized epileptic signature in case of complex decisions. Show more

Keywords: Epileptic signature, Epileptic Network, Feature Selection, Fuzzy Logic, EEGLAB

DOI: 10.3233/FI-2020-1968

Citation: Fundamenta Informaticae, vol. 176, no. 2, pp. 141-166, 2020

Authors: Przybyszewski, Andrzej W. | Chudzik, Artur | Szlufik, Stanislaw | Habela, Piotr | Koziorowski, Dariusz M.

Article Type: Research Article

Abstract: Parkinson’s disease (PD) is the second after Alzheimer’s most popular neurodegenerative disease (ND). Cures for both NDs are currently unavailable. OBJECTIVE: The purpose of our study was to predict the results of different PD patients’ treatments in order to find an optimal one. METHODS: We have compared rough sets (RS) and others, in short, machine learning (ML) models to describe and predict disease progression expressed as UPDRS values (Unified Parkinson’s Disease Rating Scale) in three groups of Parkinson’s patients: 23 BMT (Best Medical Treatment) patients on medication; 24 DBS patients on medication and on DBS therapy (Deep Brain …Stimulation) after surgery performed during our study; and 15 POP (Postoperative) patients who had had surgery earlier (before the beginning of our research). Every PD patient had three visits approximately every six months. The first visit for DBS patients was before surgery. On the basis of the following condition attributes: disease duration, saccadic eye movement parameters, and neuropsychological tests: PDQ39 (Parkinson’s Disease Questionnaire - disease-specific health-related quality-of-life questionnaire), and Epworth Sleepiness Scale tests we have estimated UPDRS changes (as the decision attribute). RESULTS: By means of RS rules obtained for the first visit of BMT/DBS/POP patients, we have predicted UPDRS values in the following year (two visits) with global accuracy of 70% for both BMT visits; 56% for DBS, and 67%, 79% for POP second and third visits. The accuracy obtained by ML models was generally in the same range, but it was calculated separately for different sessions (MedOFF/MedON). We have used RS rules obtained in BMT patients to predict UPDRS of DBS patients; for the first session DBSW1: global accuracy was 64%, for the second DBSW2: 85% and the third DBSW3: 74% but only for DBS patients during stimulation-ON. ML models gave better accuracy for DBSW1/W2 session S1(MedOFF): 88%, but inferior results for session S3 (MedON): 58% and 54%. Both RS and ML could not predict UPDRS in DBS patients during stimulation-OFF visits because of differences in UPDRS. By using RS rules from BMT or DBS patients we could not predict UPDRS of POP group, but with certain limitations (only for MedON), we derived such predictions for the POP group from results of DBS patients by using ML models (60%). SIGNIFICANCE: Thanks to our RS and ML methods, we were able to predict Parkinson’s disease (PD) progression in dissimilar groups of patients with different treatments. It might lead, in the future, to the discovery of universal rules of PD progression and optimise the treatment. Show more

Keywords: Neurodegenerative disease, rough set, decision rules, granularity

DOI: 10.3233/FI-2020-1969

Citation: Fundamenta Informaticae, vol. 176, no. 2, pp. 167-181, 2020

Authors: Chapaneri, Santosh | Jayaswal, Deepak

Article Type: Research Article

Abstract: Modeling the music mood has wide applications in music categorization, retrieval, and recommendation systems; however, it is challenging to computationally model the affective content of music due to its subjective nature. In this work, a structured regression framework is proposed to model the valence and arousal mood dimensions of music using a single regression model at a linear computational cost. To tackle the subjectivity phenomena, a confidence-interval based estimated consensus is computed by modeling the behavior of various annotators (e.g. biased, adversarial) and is shown to perform better than using the average annotation values. For a compact feature representation of …music clips, variational Bayesian inference is used to learn the Gaussian mixture model representation of acoustic features and chord-related features are used to improve the valence estimation by probing the chord progressions between chroma frames. The dimensionality of features is further reduced using an adaptive version of kernel PCA. Using an efficient implementation of twin Gaussian process for structured regression, the proposed work achieves a significant improvement in R 2 for arousal and valence dimensions relative to state-of-the-art techniques on two benchmark datasets for music mood estimation. Show more

Keywords: Music mood, Structured regression, Crowdsourced annotations

DOI: 10.3233/FI-2020-1970

Citation: Fundamenta Informaticae, vol. 176, no. 2, pp. 183-203, 2020