In this paper the existence or nonexistence of isomorphic mappings between graph models for the untyped lambda calculus is studied. It is shown that Engeler's D A is completely determined, up to isomorphism, by the cardinality of its `atom-set' A. A similar characterization is given for a collection of graph models of the Pω-type; from this some propositions regarding automorphisms are obtained. Also we give an indication of the complexity of the first-order theory of graph models by showing that (...) the second-order theory of first-order definable elements of a graph model is first-order expressable in the model. (shrink)

We present results from numerical studies of supervised learning operations in recurrent networks considered as graphs, leading from a given set of input conditions to predetermined outputs. Graphs that have optimized their output for particular inputs with respect to predetermined outputs are asymptotically stable and can be characterized by attractors which form a representation space for an associative multiplicative structure of input operations. As the mapping from a series of inputs onto a series of such attractors generally depends (...) on the sequence of inputs, this structure is generally noncommutative. Moreover, the size of the set of attractors, indicating the complexity of learning, is found to behave non-monotonically as learning proceeds. A tentative relation between this complexity and the notion of pragmatic information is indicated. (shrink)

We show that for random bit strings, Up, with probability, image, the first order quantifier depth D) needed to distinguish non-isomorphic structures is Θ, with high probability. Further, we show that, with high probability, for random ordered graphs, G≤,p with edge probability image, D)=Θ, contrasting with the results for random graphs, Gp, given by Kim et al. [J.H. Kim, O. Pikhurko, J. Spencer, O. Verbitsky, How complex are random graphs in first order logic? Random Structures and Algorithms (...) 26 119–145] of D)=log1/pn+O. (shrink)

We show that for random bit strings, Up, with probability, image, the first order quantifier depth D) needed to distinguish non-isomorphic structures is Θ, with high probability. Further, we show that, with high probability, for random ordered graphs, G≤,p with edge probability image, D)=Θ, contrasting with the results for random graphs, Gp, given by Kim et al. [J.H. Kim, O. Pikhurko, J. Spencer, O. Verbitsky, How complex are random graphs in first order logic? Random Structures and Algorithms (...) 26 119–145] of D)=log1/pn+O. (shrink)

We recall and improve our 2019 and 2020 concepts of n-SuperHyperGraph, Plithogenic nSuperHyperGraph, n-Power Set of a Set, and we present some application from the real world. The nSuperHyperGraph is the most general form of graph today and it is able to describe the complex reality we live in, by using n-SuperVertices (groups of groups of groups etc.) and nSuperHyperEdges (edges connecting groups of groups of groups etc.).

A completeness theory for parameterized computational complexity has been studied in a series of recent papers, and has been shown to have many applications in diverse problem domains including familiar graph-theoretic problems, VLSI layout, games, computational biology, cryptography, and computational learning [ADF,BDHW,BFH, DEF,DF1-7,FHW,FK]. We here study the parameterized complexity of two kinds of problems: (1) problems concerning parameterized computations of Turing machines, such as determining whether a nondeterministic machine can reach an accept state in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} (...) \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $k$\end{document} steps (the Short TM Computation Problem), and (2) problems concerning derivations and factorizations, such as determining whether a word \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $x$\end{document} can be derived in a grammar \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $G$\end{document} in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $k$\end{document} steps, or whether a permutation has a factorization of length \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $k$\end{document} over a given set of generators. We show hardness and completeness for these problems for various levels of the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $W$\end{document} hierarchy. In particular, we show that Short TM Computation is complete for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $W[1]$\end{document}. This gives a new and useful characterization of the most important of the apparently intractable parameterized complexity classes. (shrink)

Limiting identification of r.e. indexes for r.e. languages (from a presentation of elements of the language) and limiting identification of programs for computable functions (from a graph of the function) have served as models for investigating the boundaries of learnability. Recently, a new approach to the study of "intrinsic" complexity of identification in the limit has been proposed. This approach, instead of dealing with the resource requirements of the learning algorithm, uses the notion of reducibility from recursion theory to (...) compare and to capture the intuitive difficulty of learning various classes of concepts. Freivalds, Kinber, and Smith have studied this approach for function identification and Jain and Sharma have studied it for language identification. The present paper explores the structure of these reducibilities in the context of language identification. It is shown that there is an infinite hierarchy of language classes that represent learning problems of increasing difficulty. It is also shown that the language classes in this hierarchy are incomparable, under the reductions introduced, to the collection of pattern languages. Richness of the structure of intrinsic complexity is demonstrated by proving that any finite, acyclic, directed graph can be embedded in the reducibility structure. However, it is also established that this structure is not dense. The question of embedding any infinite, acyclic, directed graph is open. (shrink)

Limiting identification of r.e. indexes for r.e. languages and limiting identification of programs for computable functions have served as models for investigating the boundaries of learnability. Recently, a new approach to the study of "intrinsic" complexity of identification in the limit has been proposed. This approach, instead of dealing with the resource requirements of the learning algorithm, uses the notion of reducibility from recursion theory to compare and to capture the intuitive difficulty of learning various classes of concepts. Freivalds, (...) Kinber, and Smith have studied this approach for function identification and Jain and Sharma have studied it for language identification. The present paper explores the structure of these reducibilities in the context of language identification. It is shown that there is an infinite hierarchy of language classes that represent learning problems of increasing difficulty. It is also shown that the language classes in this hierarchy are incomparable, under the reductions introduced, to the collection of pattern languages. Richness of the structure of intrinsic complexity is demonstrated by proving that any finite, acyclic, directed graph can be embedded in the reducibility structure. However, it is also established that this structure is not dense. The question of embedding any infinite, acyclic, directed graph is open. (shrink)

Graph theory is one of those subjects that is a vital part of the digital world. It is used to monitor the movement of robots on a network, to debug computer networks, to develop algorithms, and to analyze the structural properties of chemical structures, among other things. It is also useful in airplane scheduling and the study of diffusion mechanisms. The parameters computed in this article are very useful in pattern recognition and image processing. A number d f, w = (...) min d w, t, d w, s is referred as distance between f = t s an edge and w a vertex. d w, f 1 ≠ d w, f 2 implies that two edges f 1, f 2 ∈ E are resolved by node w ∈ V. A set of nodes A is referred to as an edge metric generator if every two links/edges of Γ are resolved by some nodes of A and least cardinality of such sets is termed as edge metric dimension, e dim Γ for a graph Γ. A set B of some nodes of Γ is a mixed metric generator if any two members of V ∪ E are resolved by some members of B. Such a set B with least cardinality is termed as mixed metric dimension, m dim Γ. In this paper, the metric dimension, edge metric dimension, and mixed metric dimension of dragon graph T n, m, line graph of dragon graph L T n, m, paraline graph of dragon graph L S T n, m, and line graph of line graph of dragon graph L L T n, m have been computed. It is shown that these parameters are constant, and a comparative analysis is also given for the said families of graphs. (shrink)

We consider three problems concerning alpha conversion of closed terms (combinators). (1) Given a combinator M find the an alpha convert of M with a smallest number of distinct variables. (2) Given two alpha convertible combinators M and N find a shortest alpha conversion of M to N. (3) Given two alpha convertible combinators M and N find an alpha conversion of M to N which uses the smallest number of variables possible along the way. We obtain the following results. (...) (1) There is a polynomial time algorithm for solving problem (1). It is reducible to vertex coloring of chordal graphs. (2) Problem (2) is co-NP complete (in recognition form). The general feedback vertex set problem for digraphs is reducible to problem (2). (3) At most one variable besides those occurring in both M and N is necessary. This appears to be the folklore but the proof is not familiar. A polynomial time algorithm for the alpha conversion of M to N using at most one extra variable is given. There is a tradeoff between solutions to problem (2) and problem (3) which we do not fully understand. (shrink)

A Ramsey statement denoted \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${n \longrightarrow (k)^2_2}$$\end{document} says that every undirected graph on n vertices contains either a clique or an independent set of size k. Any such valid statement can be encoded into a valid DNF formula RAM(n, k) of size O(nk) and with terms of size \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\left(\begin{smallmatrix}k\\2\end{smallmatrix}\right)}$$\end{document}. Let rk be the minimal n for which the statement holds. We prove that (...) RAM(rk, k) requires exponential size constant depth Frege systems, answering a problem of Krishnamurthy and Moll [15]. As a consequence of Pudlák’s work in bounded arithmetic [19] it is known that there are quasi-polynomial size constant depth Frege proofs of RAM(4k, k), but the proof complexity of these formulas in resolution R or in its extension R(log) is unknown. We define two relativizations of the Ramsey statement that still have quasi-polynomial size constant depth Frege proofs but for which we establish exponential lower bound for R. (shrink)

The study of graph structure has advanced in recent years with great strides: finite graphs can be described algebraically, enabling them to be constructed out of more basic elements. Separately the properties of graphs can be studied in a logical language called monadic second-order logic. In this book, these two features of graph structure are brought together for the first time in a presentation that unifies and synthesizes research over the last 25 years. The author not only provides (...) a thorough description of the theory, but also details its applications, on the one hand to the construction of graph algorithms, and, on the other to the extension of formal language theory to finite graphs. Consequently the book will be of interest to graduate students and researchers in graph theory, finite model theory, formal language theory, and complexity theory. (shrink)

The descriptive complexity of a problem is the complexity of describing the problem in some logical formalism. One of the few techniques for proving separation results in descriptive complexity is to make use of games on graphs played between two players, called the spoiler and the duplicator. There are two types of these games, which differ in the order in which the spoiler and duplicator make various moves. In one of these games, the rules seem to (...) be tilted towards favoring the duplicator. These seemingly more favorable rules make it easier to prove separation results, since separation results are proven by showing that the duplicator has a winning strategy. In this paper, the relationship between these games is investigated. It is shown that in one sense, the two games are equivalent. Specifically, each family of graphs used in one game to prove a separation result can in principle be used in the other game to prove the same result. This answers an open question of Ajtai and the author from 1989. It is also shown that in another sense, the games are not equivalent, in that there are situations where the spoiler requires strictly more resources to win one game than the other game. This makes formal the informal statement that one game is easier for the duplicator to win. (shrink)

Impaired neurodevelopmental outcome, in particular cognitive impairment, after neonatal hypoxic-ischemic encephalopathy is a major concern for parents, clinicians, and society. This study aims to investigate the potential benefits of using advanced quantitative electroencephalography analysis for early prediction of cognitive outcomes, assessed here at 2 years of age. EEG data were recorded within the first week after birth from a cohort of twenty infants with neonatal hypoxic-ischemic encephalopathy. A proposed regression framework was based on two different sets of features, namely graph-theoretical (...) features derived from the weighted phase-lag index and entropies metrics represented by sample entropy, permutation entropy, and spectral entropy. Both sets of features were calculated within the noise-assisted multivariate empirical mode decomposition domain. Correlation analysis showed a significant association in the delta band between the proposed features, graph attributes and entropy features from the neonatal EEG data and the cognitive development at age two years. These features were used to train and test the tree ensemble regression models. The highest prediction performance was reached to 14.27 root mean square error, 12.07 mean absolute error, and 0.45 R-squared using the entropy features with a boosted tree regression model. Thus, the results demonstrate that the proposed qEEG features show the state of brain function at an early stage; hence, they could serve as predictive biomarkers of later cognitive impairment, which could facilitate identifying those who might benefit from early targeted intervention. (shrink)

Pleiotropy, in which one mutation causes multiple phenotypes, has traditionally been seen as a deviation from the conventional observation in which one gene affects one phenotype. Epistasis, or gene–gene interaction, has also been treated as an exception to the Mendelian one gene–one phenotype paradigm. This simplified perspective belies the pervasive complexity of biology and hinders progress toward a deeper understanding of biological systems. We assert that epistasis and pleiotropy are not isolated occurrences, but ubiquitous and inherent properties of biomolecular (...) networks. These phenomena should not be treated as exceptions, but rather as fundamental components of genetic analyses. A systems level understanding of epistasis and pleiotropy is, therefore, critical to furthering our understanding of human genetics and its contribution to common human disease. Finally, graph theory offers an intuitive and powerful set of tools with which to study the network bases of these important genetic phenomena. (shrink)

The number of edges in a shortest walk from one vertex to another vertex of a connected graph G is known as the distance between them. For a vertex x and an edge e = a b in G, the minimum number from distances of x with a and b is said to be the distance between x and e. A vertex x is said to distinguish two distinct edges e 1 and e 2 if the distance between x and (...) e 1 is different from the distance between x and e 2. A set X of vertices in a connected graph G is an edge metric generator for G if every two edges of G are distinguished by some vertex in X. The number of vertices in such a smallest set X is known as the edge metric dimension of G. In this article, we solve the edge metric dimension problem for certain classes of planar graphs. (shrink)

In organisms, ribonucleic acid plays an essential role. Its function is being discovered more and more. Due to the conserved nature of RNA sequences, its function mainly depends on the RNA secondary structure. The discovery of an approximate relationship between two RNA secondary structures helps to understand their functional relationship better. It is an important and urgent task to explore structural similarities from the graphical representation of RNA secondary structures. In this paper, a novel graphical analysis method based on the (...) triple vector curve representation of RNA secondary structures is proposed. A combinational method involving a discrete wavelet transform and fractal dimension with sliding window is introduced to analyze and compare the graphs derived from feature extraction; after that, the distance matrix is generated. Then, the distance matrix is analyzed by clustering and visualized as a clustering tree. RNA virus and noncoding RNA datasets are applied to perform experiments and analyze the clustering tree. The results show that the proposed method yields more accurate results in the comparison of RNA secondary structures. (shrink)

The study of the autonomic nervous system (ANS) function has shown to provide useful indicators for risk stratification and early detection on a variety of cardiovascular pathologies. However, data gathered during different tests of the ANS are difficult to analyse, mainly due to the complex mechanisms involved in the autonomic regulation of the cardiovascular system (CVS). Although model-based analysis of ANS data has been already proposed as a way to cope with this complexity, only a few models coupling the (...) main elements involved have been presented in the literature. In this paper, a new model of the CVS, representing the ventricles, the circulatory system and the regulation of the CVS activity by the ANS, is presented. The models of the vascular system and the ventricular activity have been developed using the Bond Graph formalism, as it proposes a unified representation for all energetic domains, facilitating the integration of mechanic and hydraulic phenomena. In order to take into account the electro-mechanical behaviour of both ventricles, an electrophysiologic model of the cardiac action potential, represented by a set of ordinary differential equations, has been integrated. The short-term ANS regulation of heart rate, cardiac contractility and peripheral vasoconstriction is represented by means of continuous transfer functions. These models, represented in different continuous formalisms, are coupled by using a multi-formalism simulation library. Results are presented for two different autonomic tests, namely the Tilt Test and the Valsalva Manoeuvre, by comparing real and simulated signals. (shrink)

The primary objective of this study was to propose a functional discrete mathematical model for analyzing folklore fairy tales. Within this model, characters are denoted as vertices, and explicit instances of communication – both verbal and non-verbal – within the text are depicted as edges. Upon examining a corpus of Eastern Slavic fairy tales in comparison to Chukchi fairy tales, unforeseen outcomes emerged. Notably, the constructed models seem to evade establishing certain connections between characters. Consequently, instances where the interactions among (...) fairy tale characters would result in a non-planar graph structure are notably absent. To put it differently, the models refrain from incorporating sub-graphs delineated by the Kuratowski theorem governing planar graphs, specifically the minimal non-planar graphs Κ5 and Κ3,3. Remarkably, even in more extensive texts featuring a larger cast of characters, connections that would yield a non-planar graph pattern are consistently avoided. This leads to the formulation of a hypothesis positing that traditional folk tales adhere to a “planar narrative” design – an identifiable narrative variant characterized by inherent limitations in complexity. This design, in turn, appears deeply entrenched within the societal framework of the cultures that produced these folk narratives. (shrink)

This paper presents a Conceptual Graph (CG) framework to the Generation of Referring Expressions (GRE). Employing Conceptual Graphs as the underlying formalism allows a rigorous, semantically rich, approach to GRE. A number of advantages over existing work are discussed. The new framework is also used to revisit existing complexity results in a fully rigorous way, showing that the expressive power of CGs does not increase the theoretical complexity of GRE.

Since Sun-Joo Shin's groundbreaking study (2002), Peirce's existential graphs have attracted much attention as a way of writing logic that seems profoundly different from our usual logical calculi. In particular, Shin argued that existential graphs enjoy a distinctive property that marks them out as "diagrammatic": they are "multiply readable," in the sense that there are several di erent, equally legitimate ways to translate one and the same graph into a standard logical language. Stenning (2000) and Bellucci and Pietarinen (...) (2016) have retorted that similar phenomena of multiple readability can arise for sentential notations as well. Focusing on the simplest kinds of existential graphs, called alpha graphs (AGs), this paper argues that multiple readability does point to important features of AGs, but that both Shin and her critics have misdiagnosed its source. As a preliminary, and because the existing literature often glosses over such issues, we show that despite their non-linearity, AGs are uniquely parsable and allow for inductive de nitions. Extending earlier discussions, we then show that that in principle, all propositional calculi are multiply readable, just like AGs: contrary to what has been suggested in the literature, multiple readability is linked neither to non-linearity nor to AGs' dearth of connectives. However, we argue that in practice, AGs are more amenable to multiple readability than our usual notations, because the patterns that one needs to recognize to multiply translate an AG form what we call complex symbols, whose structural properties make it easy to perceive and process them as units. Nevertheless, we show that such complex symbols, though largely absent from our usual notations, are not inherently diagrammatic and can be found in seemingly sentential languages. Hence, while ultimately vindicating Shin's idea of multiple readability, our analysis traces it to a di erent source and thus severs its link with diagrammaticity. (shrink)

The study of the autonomic nervous system (ANS) function has shown to provide useful indicators for risk stratification and early detection on a variety of cardiovascular pathologies. However, data gathered during different tests of the ANS are difficult to analyse, mainly due to the complex mechanisms involved in the autonomic regulation of the cardiovascular system (CVS). Although model-based analysis of ANS data has been already proposed as a way to cope with this complexity, only a few models coupling the (...) main elements involved have been presented in the literature. In this paper, a new model of the CVS, representing the ventricles, the circulatory system and the regulation of the CVS activity by the ANS, is presented. The models of the vascular system and the ventricular activity have been developed using the Bond Graph formalism, as it proposes a unified representation for all energetic domains, facilitating the integration of mechanic and hydraulic phenomena. In order to take into account the electro-mechanical behaviour of both ventricles, an electrophysiologic model of the cardiac action potential, represented by a set of ordinary differential equations, has been integrated. The short-term ANS regulation of heart rate, cardiac contractility and peripheral vasoconstriction is represented by means of continuous transfer functions. These models, represented in different continuous formalisms, are coupled by using a multi-formalism simulation library. Results are presented for two different autonomic tests, namely the Tilt Test and the Valsalva Manoeuvre, by comparing real and simulated signals. (shrink)

The study of the autonomic nervous system (ANS) function has shown to provide useful indicators for risk stratification and early detection on a variety of cardiovascular pathologies. However, data gathered during different tests of the ANS are difficult to analyse, mainly due to the complex mechanisms involved in the autonomic regulation of the cardiovascular system (CVS). Although model-based analysis of ANS data has been already proposed as a way to cope with this complexity, only a few models coupling the (...) main elements involved have been presented in the literature. In this paper, a new model of the CVS, representing the ventricles, the circulatory system and the regulation of the CVS activity by the ANS, is presented. The models of the vascular system and the ventricular activity have been developed using the Bond Graph formalism, as it proposes a unified representation for all energetic domains, facilitating the integration of mechanic and hydraulic phenomena. In order to take into account the electro-mechanical behaviour of both ventricles, an electrophysiologic model of the cardiac action potential, represented by a set of ordinary differential equations, has been integrated. The short-term ANS regulation of heart rate, cardiac contractility and peripheral vasoconstriction is represented by means of continuous transfer functions. These models, represented in different continuous formalisms, are coupled by using a multi-formalism simulation library. Results are presented for two different autonomic tests, namely the Tilt Test and the Valsalva Manoeuvre, by comparing real and simulated signals. (shrink)

I examine to what extent accounts of mechanisms based on formal interventionist theories of causality can adequately represent biological mechanisms with complex dynamics. Using a differential equation model for a circadian clock mechanism as an example, I first show that there exists an iterative solution that can be interpreted as a structural causal model. Thus, in principle, it is possible to integrate causal difference-making information with dynamical information. However, the differential equation model itself lacks the right modularity properties for a (...) full integration. A formal mechanistic model will therefore have to leave out either noncausal or causal explanatory relations. (shrink)

I examine the adequacy of the causal graph-structural equations approach to causation for modeling biological mechanisms. I focus in particular on mechanisms with complex dynamics such as the PER biological clock mechanism in Drosophila. I show that a quantitative model of this mechanism that uses coupled differential equations – the well-known Goldbeter model – cannot be adequately represented in the standard causal graph framework, even though this framework does permit causal cycles. The reason is that the model contains dynamical information (...) about the mechanism that concerns causal properties but that does not correspond to variables that could be subject to independent interventions. Thus, a representation of the mechanisms as a causal structural model necessarily suppresses causally relevant information. (shrink)

Bipolar argument graphs represent the structure of complex pro and contra arguments for one or more standpoints. In this article, ampliative and exclusionary principles of evaluating argument strength in bipolar acyclic argumentation graphs are laid out and compared to each other. Argument chains, linked arguments, link attackers and supporters, and convergent arguments are discussed. The strength of conductive arguments is also addressed but it is argued that more work on this type of argument is needed to properly distinguish (...) argument strength from more general value-based components of such arguments. The overall conclusion of the article is that there is no justifiably unique solution to the problem of argument strength outside of a particular epistemological framework. (shrink)

In recent years, the research of wavelet frames on the graph has become a hot topic in harmonic analysis. In this paper, we mainly introduce the relevant knowledge of the wavelet frames on the graph, including relevant concepts, construction methods, and related theory. Meanwhile, because the construction of graph tight framelets is closely related to the classical wavelet framelets on ℝ, we give a new construction of tight frames on ℝ. Based on the pseudosplines of type II, we derive an (...) MRA tight wavelet frame with three generators ψ 1, ψ 2, and ψ 3 using the oblique extension principle, which generate a tight wavelet frame in L 2 ℝ. We analyze that three wavelet functions have the highest possible order of vanishing moments, which matches the order of the approximation order of the framelet system provided by the refinable function. Moreover, we introduce the construction of the Haar basis for a chain and analyze the global orthogonal bases on a graph G. Based on the sequence of framelet generators in L 2 ℝ and the Haar basis for a coarse-grained chain, the decimated tight framelets on graphs can be constructed. Finally, we analyze the detailed construction process of the wavelet frame on a graph. (shrink)

The aim of this paper is to elucidate the mereological structure of complex states of affairs without relying on the problematic notion of structural universals. For this task tools from graph theory, lattice theory, and the theory of relational systems are employed. Our starting point is the mereology of similarity structures. Since similarity structures are structured sets, their mereology can be considered as a generalization of the mereology of sets..

We show that there exist 2 ℵ 0 equational classes of Boolean algebras with operators that are not generated by the complex algebras of any first-order definable class of relational structures. Using a variant of this construction, we resolve a long-standing question of Fine, by exhibiting a bimodal logic that is valid in its canonical frames, but is not sound and complete for any first-order definable class of Kripke frames (a monomodal example can then be obtained using simulation results of (...) Thomason). The constructions use the result of Erd $\H{o}$ s that there are finite graphs with arbitrarily large chromatic number and girth. (shrink)

Nowadays, the development of big data is getting faster and faster, and the related research on motion sensing recognition and complex systems under the background of big data is gradually being valued. At present, there are relatively few related researches on vertical Baduanjin in the academic circles; research in this direction can make further breakthroughs in motion sensor recognition. In order to carry out related action recognition research on the lifting action of vertical Baduanjin, this paper uses sensor technology to (...) collect the motion video image of vertical Baduanjin based on the background of big data and uses action recognition technology and related algorithms to obtain the action. Recognize the video image to obtain the data, get the acceleration, angular velocity, and EMG data, and count the end time and duration according to the change of the action. According to the data table and graph change trend compiled at the end of the experiment, we can see the following: after the data is preprocessed, the acceleration signal change range is limited to [−1, 1], and the acceleration change has a clear directionality; and, after 15 lifts of the detected object, its angular velocity in X-axis direction is basically negative. However, when the ninth lift is performed, the angular velocity of the movement in X-axis direction is 36.09, the largest of all angular velocities. When performing the 15th lifting action, the angular velocity of this action in Z-axis direction is −26.05, which is the smallest of all angular velocities. The longest duration of the left muscle discharge during the lifting action of the subject is 15.24 for the tibial anterior muscle and 8.91 for the external oblique muscle with the shortest duration. The longest discharge duration of the right muscle is also the tibial anterior muscle with 12.15, and the shortest duration is the erector spinae with 8.79. (shrink)

Several results about the game of cops and robbers on infinite graphs are analyzed from the perspective of computability theory. Computable robber-win graphs are constructed with the property that no computable robber strategy is a winning strategy, and such that for an arbitrary computable ordinal \, any winning strategy has complexity at least \}\). Symmetrically, computable cop-win graphs are constructed with the property that no computable cop strategy is a winning strategy. Locally finite infinite trees and (...) graphs are explored. The Turing computability of a binary relation used to classify cop-win graphs is studied, and the computational difficulty of determining the winner for locally finite computable graphs is discussed. (shrink)

This work deals with the expressive power of logics on finite graphs with access to an additional "arbitrary" linear order. The queries that can be expressed this way are the order-invariant queries for the logic. For the standard logics used in computer science, such as first-order logic, it is known that access to an arbitrary linear order increases the expressiveness of the logic. However, when we look at the separating examples, we find that they have satisfying models whose Gaifman (...) Graph is complex -unbounded in valence and in treewidth. We thus explore the expressiveness of order-invariant queries over well-behaved graphs. We prove that first-order order-invariant queries over strings and trees have no additional expressiveness over first-order logic in the original signature. We also prove new upper bounds on order-invariant queries over bounded treewidth and bounded valence graphs. Our results make use of a new technique of independent interest: the application of algebraic characterizations of definability to show collapse results. (shrink)