bluuebunny/crossref_metadata_2025 huggingface dataset:
Greenhouse Gas Emissions from Piggery and Biogas Digesters in the North of Vietnam
Authors: Dung Pham Van , Hoan Duong Cong , Arango Jacobo , Tran Nghia Dai , Nguyen Kien Tri , Arevalo Ashly , Douxchamps Sabine
Published: May 2021

Increases in pig farm densities have caused great pressures on waste management systems and produce massive manure and urine quantities in Vietnam. This study aimed to identify the role and contributions of biogas digesters to better manage the sources of greenhouse gas (GHG) emissions from pig wastes for different types of pig farms in the north of Vietnam. Four provinces, namely Thanh Hoa, Phu Tho, Thai Binh, Vinh Phuc, were identified. A total of 24 farms were purposively selected including 16 small-size farms and 8 larger-size farms. The findings showed that GHG emissions from small-size farms (154.8 t CO2-eq.yr-1) did not significantly differ from the amounts measured in larger-size farms (139.1 t CO2-eq.yr-1) in the four surveyed provinces. The sampling position did not significantly affect the GHG emission rates, with 173.9 t CO2-eq.yr-1 inside piggeries and 120.8 t CO2-eq.yr-1 outside the outlet of the biogas digesters (p-value=0.09). N2O emissions require further measurements at different farm sizes and sites. These results confirmed that the pig waste management of biogas digesters for both small-size and larger-size pig farms is not completely efficient and that efforts need to be invested in to mitigate GHG emissions in pig production. Reducing pig density per piggery is highly recommended. The application of other alternative aerobic or anaerobic digestion technologies like vermicompost, effective microorganisms, and composting should also be encouraged and promoted.
Modified Atmosphere Packaging Reduces Pericarp Browning and Maintains the Quality of ‘Huong Chi’ Longan Fruit (Dimocarpus Longan) Pretreated with Citric Acid
Authors: Thuy Nguyen Thi Bich , Hanh Nguyen Thi
Published: May 2021

Longan ‘Huong Chi’ (Dimocarpus longan Lour.) is one of the most favorite and widely exported fruits in Vietnam, but the trading of longan faces considerable challenges due to rapid pericarp browning and decay. Our study aimed to determine the effects of modified atmospheres generated by low-density polyethylene (LDPE), polypropylene bag (PP), and LifeSpan L201 films on the quality and pericarp browning of ‘Huong Chi’ longan fruit pre-treated with 3.0 % citric acid and stored at 5oC. The results showed that LifeSpan L201 and LDPE packaging created an equilibrium atmosphere of 10.66 ± 0.78% O2, 4.44 ± 0.64% CO2, and 15.04 ± 0.89% O2, 2.96 ± 0.61% CO2,  respectively. The modified atmospheres generated by LifeSpan L201 and LDPE delayed pericarp browning, maintained the total soluble solids (TSS) and vitamin C content, and reduced decay in longan fruit. Meanwhile, the PP packaging resulted in an improperly modified atmosphere which led to severe decay and browning in cold storage conditions.
An Application of Image Processing in Optical Mark Recognition
Authors: Ha Tran Vu , Thu Nguyen Thi
Published: May 2021

The Optical Mark Recognition (OMR) is very popular with universities for the reading of multiple-choice questions. In this article, we presented a software system for processing surveys at the Vietnam National University of Agriculture based on digital image processing. This software was built using MATLAB and easy to use. The surveys were digitized using a scanner and sent to the software tool. In this study, we tested more than 170 surveys of nine different types. The software tool correctly detected all the valid answers. It was also able to detect all questions with no or multiple marks.
The Domestic Solid Waste Management Following Circular Economy Model
Authors: Quynh Nguyen Thi Thu , Hung Nguyen Quoc
Published: May 2021

Along with socio-economic development, the volume of domestic solid waste in Vietnam is increasing by 12% annually. The current management model of domestic solid waste presents many limitations: low collection rate, lack of proper treatment, and low levels of recycling and reusing rates but high rates of buried waste and pollution. Published research and overviews of practical implementation of solid waste management models in typical countries around the world have shown the need to innovate domestic solid waste management in Vietnam following the circular economy model to increase the economic efficiency of resources and to minimize polluting the environment. Accordingly, state management of domestic solid waste needs to be reformed synchronously to ensure the development of a closed cycle of waste from identifying generators, classifying waste at sources, collecting, transporting, and treating waste, to the consumption of recycled waste.
A Review of Cunninghamia lanceolata (Lamb.) Hook: A Recent Update and Potential Application in Vietnam
Authors: Da Tran Binh , Ha Le Thi Ngoc
Published: May 2021

By reviewing worldwide literature, this paper aimed to systematically collate available information about the species Cunninghamia lanceolata. Based on the findings of the review, including the species’ floral characteristics; updated distribution; historical knowledge and heritage; growth and factors influencing its forests; soil nutrition and microbes; carbon storage; wood; and chemicals and essential oils, we have identified issues for consideration regarding the use of this species for big timber production in Vietnam. We propose that it is suitable for a range of applications: for small or large timber plantations, mono/mixed plantations, and agroforestry. If planted at lower altitudes or warmer temperatures, its growth is likely to be improved, but seed production may be less successful. Cultivation of this species for big timber production should be undertaken according to silviculture best practices, ensuring good seed quality, a suitable stand density, and appropriate fertilization thinning strategies, in support of government policies and in accordance with current science and technology.
Trends in Attention to the 17 Sustainable Development Goals of the United Nations
Authors: Wankel Charles , Stachowicz-Stanusch Agata
Published: May 2021

In 2015 the United Nations put forth 17 Sustainable Development Goals (SDGs). These are intended to be largely achieved by 2030. The Sustainable Development Goals are a larger follow-up to the United Nations’ Millennial Development Goals (MDGs), agreed to 2000, which were the first attempt by the UN to create metrics for improving societies that were to be used across the world (From MDGs to SDGs, n.d.). This study is on trends in attention to the SDGs, as indicated by trends in the production of academic articles on the topical areas of each of the 17 SDGs. Research related to the Sustainable Development Goals is important to see what is being prioritized and what needs to get more focus (Fayomi, 2018). The sub-goals of the SDGs are called “indicators.” Key topics and terms of the SDGs and their indicators can be used in searching Google Scholar year by year to ascertain cardinal and ordinal measures of trends in article publication related to the SDGs. This is based on the premise that attention to a particular SDG in academic literature is a valid indicator related to action by nations, businesses, and not-for-profit organizations on the SDGs. This research aims to investigate changes in the relative attention paid to SDGs by academics as indicated in the absolute and relative numbers of articles produced over the period 2010-2020 as indicated by their listing, year by year, in the Google Scholar database. Key terms were extracted from the sub-goals of the SDGs and utilized as search terms. Two search terms were used for each SDG, ad based on the data, we then focused in on the most relevant one for each SDG to examine in comparison with the others. We compare the located continuities, changes in a relative number of items produced (change in ranking) over this time frame. Theories that might be tested in future research on the source of change in the relative ranking of the SDGs are put forth.
MODELING OF THE FATIGUE DURABILITY OF STRUCTURAL ALLOYS UNDER TWO-FREQUENCY LOADING
Authors: Shishulin D.N. , Boev E.V.
Published: May 2021

The processes of fatigue life of polycrystalline structural alloys under the combined action of low- and high-cycle fatigue mechanisms are considered. From the standpoint of damaged medium mechanics (DMM), a mathematical model has been developed that describes the processes of plastic deformation and the accumulation of fatigue damage. The DMM model consists of three interrelated parts: relations that determine the cyclic elastoplastic behavior of the material, taking into account the dependence on the fracture process; equations describing the kinetics of fatigue damage accumulation; criterion for the strength of the damaged material.
Variant of the constitutive relations for elastoplasticity is based on the concept of a microplastic loading surface in the von Mises form and the principle of the gradient of the plastic strain rate vector to the surface at the loading point. This version of the equations of state reflects the main effects of the process of cyclic plastic deformation of the material for arbitrary complex loading trajectories.
A variant of the kinetic equations for the accumulation of fatigue damage is based on the introduction of a scalar damage parameter, is based on energy principles and takes into account the main effects of the formation, growth and fusion of microdefects under arbitrary complex loading conditions. A unified form of the evolutionary equation for the accumulation of fatigue damages for low-cycle and high-cycle fatigue is proposed.
As a criterion for the strength of the damaged material, the condition for reaching the critical value of the damage is used.
To assess the reliability and determine the limits of applicability of the constitutive relations of the DMM, numerical studies of the processes of accumulation of fatigue damage by cyclic inelastic deformation and fatigue failure of steel 20 and 08Х18Н12Т were carried out under single-frequency loading of the upper frequency and two-frequency loading with different amplitude ratios. And the comparison of the obtained numerical results with the data of field experiments is carried out. The results of comparing the calculated and experimental data showed that the developed model of the damaged environment reliably describes the durability of structures under the action of low- and high-cycle fatigue mechanisms.
NUMERICAL SIMULATION OF THE ELASTIC BEHAVIOR OF SYN-CYCLE COMPOSITES BASED ON HOLLOW GLASS MICROSPHERES UNDER TENSION
Authors: Baykov A.V. , Turusov R.A. , Trofimov A.N. , Pleshkov L.V.
Published: May 2021

Using the universal software package “Solid Works”, on the example of a cubic model of a composite based on hollow glass microspheres (HGM), numerical simulation of the elastic behavior of a syntactic material under uniaxial tension is carried out. The chosen computational model is a hollow thin-walled glass sphere placed in a polymer (epoxy) matrix of cubic shape. The model was calculated using the finite-element method in an elastic approach with boundary conditions defined by the used universal software system of 3D modeling of the “Solid Works” complex. The calculations made it possible to determine the longitudinal and transverse elastic strains for the model of a syntactic composite with different contents of the initial components and then to calculate the value of the elastic modulus and the Poisson's ratio under tension for these materials.

Experimental verification of the calculations performed was carried out on samples of syntactic composites based on epoxy binder and HGM of type MC-ВП A9 2 gr. A size group of microspheres with a diameter of 50 to 70 microns was isolated from the initial HGM by sieving method. The average diameter of these microspheres was about 59 microns. On the basis of the microspheres selected in this way, samples of epoxy composites with different volume contents of components (30%, 40% and 50% HGM) were made and their actual elastic characteristics under tension were measured. The results of experiments to determine the elastic characteristics of syntactic composites correlate well with the calculations, especially for composites with a filling coefficient of 0.45–0.5 with hollow microspheres.
ANALYTICAL AND NUMERICAL STUDIES OF FREE VIBRATIONS OF CYLINDRICAL SHELL WITH ACOUSTIC MEDIUM
Authors: Dyachenko I.A. , Mironov A.A.
Published: May 2021

The research materials are related to the problem of ensuring vibration resistance of pipelines exposed to dynamic loads, for which increased vibration is the main cause of damage. The solution to this problem involves studying the parameters of free vibrations of the structure. The paper solves the problem of determining the natural frequencies and forms of vibrations of a section of a circular cylindrical shell filled with an medium considered in the acoustic approximation. The results of studies of the parameters of free vibrations were obtained both by the analytical method of shell theory based on the Kirchhoff-Love hypotheses, and using the finite element complex of engineering analysis ANSYS. It is shown that the influence of the medium density on the parameters of free vibrations of the shell depends on the ratio of the shell thickness to its radius it turns out to be significant only for the shape of vibrations associated with bending deformation, and insignificant for forms associated with deformations of the middle layer. A comparative analysis of the results of calculations obtained for models of compressible and incompressible medium shows that when solving the problem of determining the parameters of free vibrations of the shell, the compressibility of the medium can be neglected. At the same time, to solve practical problems that require taking into account the full spectrum of natural frequencies of the shell–medium system, a compressible medium model should be used, in which the results on the effect of shell stiffness on the frequency spectrum of the medium volume are obtained. When solving practical problems of pipeline systems vibration, the use of the finite element method in a coupled formulation is an effective tool that allows us to consider all physical processes taking into account their mutual influence on each other.
NUMERICAL ANALYSIS OF THE DYNAMICS OF THREE-DIMENSIONAL ANISOTROPIC BODIES BASED ON NON-CLASSICAL BOUNDARY INTEGRAL EQUATIONS
Authors: Belov A.A. , Petrov A.N.
Published: May 2021

The application of non-classical approach of the boundary integral equation method in combination with the integral Laplace transform in time to anisotropic elastic wave modeling is considered. In contrast to the classical approach of the boundary integral equation method which is successfully implemented for solving three-dimensional isotropic problems of the dynamic theory of elasticity, viscoelasticity and poroelasticity, the alternative nonclassical formulation of the boundary integral equations method is presented that employs regular Fredholm integral equations of the first kind (integral equations on a plane wave). The construction of such boundary integral equations is based on the structure of the dynamic fundamental solution. The approach employs the explicit boundary integral equations. The inverse Laplace transform is constructed numerically by the Durbin method. A numerical solution of the dynamic problem of anisotropic elasticity theory based on the boundary integral equations method in a nonclassical formulation is presented. The boundary element scheme of the boundary integral equations method is built on the basis of a regular integral equation of the first kind. The problem is solved in anisotropic formulation for the load acting along the normal in the form of the Heaviside function on the cube face weakened by a cubic cavity. The obtained boundary element solutions are compared with finite element solutions. Numerical results prove the efficiency of using boundary integral equations on a single plane wave in solving three-dimensional anisotropic dynamic problems of elasticity theory. The convergence of boundary element solutions is studied on three schemes of surface discretization. The achieved calculation accuracy is not inferior to the accuracy of boundary element schemes for classical boundary integral equations. Boundary element analysis of solutions for a cube with and without a cavity is carried out.
Exponential decay for the semilinear wave equation with localized frictional and Kelvin–Voigt dissipating mechanisms
Authors: Cavalcanti Marcelo M. , Gonzalez Martinez Victor H.
Published: May 2021

In the present paper, we are concerned with the semilinear viscoelastic wave equation in an inhomogeneous medium Ω subject to two localized dampings. The first one is of the type viscoelastic and is distributed around a neighborhood ω of the boundary according to the Geometric Control Condition. The second one is a frictional damping and we consider it hurting the geometric condition of control. We show that the energy of the wave equation goes uniformly and exponentially to zero for all initial data of finite energy taken in bounded sets of finite energy phase-space.
On extension of stochastic k-automata
Authors: Janicki Sławomir , Szynal Dominik
Published: May 2021

There are a great many research works concerning the well-known stochastic automata of Moore, Mealy, Rabin, Turing and others. Recently an automaton of Markov’s chain type has been introduced by Bartoszyński. This automaton is obtained by a generalization of Pawlak’s deterministic machine. The aim of this note is to give a concept of a stochastic automaton of Markov’s generalized chain type. The introduced automaton called a stochastic k-automaton (s.k-a.) is a common generalization of Bartoszyński’s automaton and Grodzki’s deterministic k-machine. By a stochastic k-automaton we mean an ordered triple M k = ⟨ U , a , π ⟩, k ⩾ 1, where U denotes a finite non-empty set, a is a function from Uk to [0, 1] with ∑ v ∈ U k a ( v ) = 1, and π is a function from Uk+1 to [0,1] with ∑ u ∈ U π ( v , u ) = 1 for every v ∈ U k . For all N ⩾ k we can define a probability measure PN on U N = U × U × … × U as follows: P N ( u 1 , u 2 , … , u N ) = a ( u 1 , u 2 , … , u k ) π ( u 1 , u 2 , … , u k + 1 ) π ( u 2 , u 3 , … , u k + 2 ) … π ( u N − k , u N − k + 1 , … , u N ). We deal with the problems of the shrinkage and the extension of a system of s.k-a.’s M k ( i ) = ⟨ U , a ( i ) , π ( i ) ⟩, i = 1 , 2 , … , m , m ⩾ 2. In this note there are given conditions under which an s.k-a. M k = ⟨ U , a , π ⟩ exists and the language of this automaton defined as L M = { ( u 1 , u 2 , u 3 , … ) : ∧ N ⩾ 1 P N ( u l , u 2 , … u N ) > 0 } either contains the languages of all the automata M k ( i ) , i = 1 , 2 , … , m, or this language equals the intersection of all those languages.
On two-dimensional data organization I1
Authors: Lodi E. , Luccio F. , Mugnai C. , Pagli L.
Published: May 2021

Two-dimensional sequential data organization is considered, where each dimension corresponds to one of two attributes. A query on the data is a figure on the storage. The elementary figure is a rectangle, and any figure can be described by a set of rectangles. Prime rectangles are defined as the ones relevant to any figure description, and the problem of finding a minimal description is studied. In particular, the upper bound to the number of prime rectangles is derived, and a cubic algorithm to find all such rectangles is given. Descriptions composed of all disjoint rectangles are the subject of the second part or this paper.
On two-dimensional data organization II1
Authors: Lipski Witold , Lodi Elena , Luccio Fabrizio , Mugnai Cristina , Pagli Linda
Published: May 2021

Following a previous Part I, two-dimensional sequential data organization is considered. A set of data is a figure on the storage. The elementary figure is the rectangle, and any figure is described by a set of rectangles. The decomposition of a figure into disjoint rectangles is studied. Some properties of the description composed of the minimum number of disjoint rectangles (MDD) are presented. It is shown that aligned edges of a figure play a fundamental role in the form of an MDD, and an algorithm is presented which constructs an MDD of an arbitrary figure in polynomial time.
SOL: an exercise in defining a language
Authors: Maggiolo-Schettini A. , Uccella G.
Published: May 2021

A language for operation on a stack (SOL) is defined formally, also from the semantic point of view. The semantics is an input-output semantics which uses functions from sequences (of integers) of indefinite length to sequences (of integers) of indefinite length as models of the computation on a stack. The programs in SOL are interpreted in recursive systems of functional definitions to which fixed point theory easily applies in order to evaluate the functions computed by the programs. The language has been implemented and used for didactic purposes.
Non-generable formal languages
Authors: Cenzer Douglas
Published: May 2021

A set A of words on a finite alphabet Σ is said to be generable if it is the closure of a computable inductive operator; in particular, if S is a semi-Thue system then the set of words derivable in S is generable. An RE set of words (equivalently, a phrase-structure or type 0 language in the sense of Chomsky [Information and Control 2 (1959), 137–167]) which is non-generable is constructed by means of a finite injury priority argument. The construction is refined to obtain a non-generable set of degree 0′ and, for any degree d, a non-generable set of degree ⩽ d.
A note on M-growth functions of FTOL systems with rank
Authors: Rozenberg Grzegorz , Vermeir Dirk
Published: May 2021

A theorem is presented which characterizes the maximal growth in FTOL systems with rank.
An algorithm of finding an acyclic f-graph for a family of sets
Authors: Truszczyński Mirosław
Published: May 2021

Acyclic families of sets are investigated. A theorem giving necessary and sufficient conditions for the family of sets to be acyclic is formulated and proved. Then an algorithm is described of finding the acyclic f-graph for a given family of sets whenever this family is acyclic. Its computational complexity is equal to O ( n 3 + n 2 k ), so it is better than the other algorithms known so far.
A Copying Theorem for ETOL Languages with Rank
Authors: Rozenberg Grzegorz , Vermeir Dirk
Published: May 2021

An infinite hierarchy within the class of ETOL languages is proved in such a way that it is spanned on an infinite sequence of ETOL languages with increasing rank where each of the languages has a length set containing the range of a strictly growing polynomial of degree 1.
On a Variant of a Method of Berstel’s and Nielsen’s
Authors: Ruohonen Keijo
Published: May 2021

An analogy to a result of J. Berstel’s and M. Nielsen’s, showing how equality of coefficient sets of certain N-rational sequences (DOL growth sequences) manifests itself by forcing equal periodical subsequences, is obtained for sequences of words. As applications, certain decidability problems for L languages are reduced to the equivalence problem for HDOL sequences.
Information Retrieval Systems, an Algebraic Approach I1
Authors: Raś Zbigniew
Published: May 2021

This paper is the first of the three parts of work on the information retrieval systems proposed by Salton (see [24]). The system is defined by the notions of a partially ordered set of requests (A, ⩽), the set of objects X and a monotonic retrieval function U : A → 2X. Different conditions imposed on the set A and a function U make it possible to obtain various classes of information retrieval systems. We will investigate systems in which (A, ⩽) is a partially ordered set, a lattice, a pseudo-Boolean algebra and Boolean algebra. In my paper these systems are called partially ordered information retrieval systems (po-systems) lattice information retrieval systems (l-systems); pseudo-Boolean information retrieval systems (pB-systems) and Boolean information retrieval systems (B-systems). The first part concerns po-systems and 1-systems. The second part deals with pB-systems and B-systems. In the third part, systems with a partial access are investigated. The present part discusses the method for construction of a set of attributes. Problems connected with the selectivity and minimalization of a set of attributes are investigated. The characterization and the properties of a set of attributes are given.
A Criterion of Undecidability of Algorithmic Theories
Authors: Dańko Wiktor
Published: May 2021

In this paper a criterion of undecidability of theories based on algorithmic logic [1,8] is formulated. By the application of this criterion we are able to assert undecidability of algorithmic theory finite fields, theories of date structures e.g. dictionaries, storage management system and others theories of structures with finite universes. It is also proved that every decidable algorithmic theory admits elimination of iteration quantifiers and examples of decidable algorithmic theories are given.
Fixed Points in the Power Set Algebra of Infinite Trees12
Authors: Tiuryn Jerzy
Published: May 2021

In this paper we are studying two notions of continuity, both are weaker than the well known and broadly applied notion of ω-continuity. The paper shows that power set algebras of finite/infinite trees provide all possible instances of the above-mentioned continuities, which depend on the signature of trees and on the substitution: OI or IO.
A Second-Order Dynamic Logic with Array Assignments
Authors: Hajek Petr , Kůrka Petr
Published: May 2021

A second-order axiomatization of dynamic logic with array assignments is presented. This axiomatization is shown to be arithmetically complete in the sense of Harel. As an example, a partial correctness assertion concerning a sorting algorithm is proved.
On Sequents Defined by Means of Information Systems
Authors: Novotný Miroslav
Published: May 2021

Information (storage and retrieval) systems lead to define sequents of formulas of the propositional calculus. By constructing the so called very simple information systems and their marked valuations, we prove that a formula β is a sequent of a formula α if and only if the formula β → α, is a tautology.
An Example of a Complete First-Order Theory with All Models Algorithmically Trivial but Without Locally Finite Models
Authors: Urzyczyn Paweł
Published: May 2021

We show an example of a first-order complete theory T, with no locally finite models and such that every program schema, total over a model of T, is strongly equivalent in that model to a loop-free schema. For this purpose we consider the notion of an algorithmically prime model, what enables us to formulate an analogue to Ryll-Nardzewski Theorem.
Constrained Petri Nets
Authors: Goeman H.J.M. , Groenwegen L.P.J. , Kleijn H.C.M. , Rozenberg G.
Published: May 2021

This paper investigates the use of sets of places of a Petri net as additional (to input places) constraints for granting concession to a transition. Various modes of using constraints give rise to various classes (of languages) of constrained Petri nets. The power of these classes is compared in the language theoretical framework.
Chain-Continuous Algebras a Variety of Partial Algebras
Authors: Pasztor Ana
Published: May 2021

We prove that the category of ω-continuous algebras of any fixed (infinitary) signature is a variety of the category of partial algebras of an adequate signature. This enables us to derive properties of ω-continuous algebras from the thoroughly investigated properties of partial algebras.
ω-Rule and Continuity on Connections Between Algebraic Semantics, Fixpoint Semantics and Algorithmic Logic
Authors: Enjalbert Patrice
Published: May 2021

Some links between algorithmic logic (AL) and algebraic semantics are examined. We show that the axioms of AL force the functions associated with programs to be fixpoints of the usual functionals, the ω-rule being indispensable for forcing the least one.
On an Application of Algorithmic Theory of Stacks
Authors: Szałas Andrzej
Published: May 2021

The fact that for every formula describing properties of programs with recursive functions there exists an equivalent while-formula with stacks is proved in a constructive way. This implies the possibility of using the algorithmic theory of stacks to prove the properties of ALGOL-like programs. The normal forms for such programs are also defined.
Propositional Logics of Formal Languages
Authors: Radev Slavian
Published: May 2021

A family of propositional logics of programs with Kripke-style semantics is introduced. A global deductive system is given and the completeness of the logics from that family is proved.
A Survey of Some Recent Results on Computational Complexity in Weak Theories of Arithmetic1
Authors: Deborah Joseph , Young Paul
Published: May 2021

In spite of the fact that much effort has been expended trying to prove lower bounds for algorithms and trying to solve the P = NP question, only limited progress has been made. Although most computer scientists remain convinced that solutions will be found, others (Hartmanis and Hopcroft, Fortune, Leivant and O’Donnell, and Phillips) have questioned the adequacy of Peano arithmetic for computer science. This uncertainty has only been increased by the recent work of Paris and Harrington showing that certain simple, finitistic, combinatorial statements are in fact independent of Peano Arithmetic. In this paper we survey complexity theoretic statements that are known to be independent of arithmetic theories. In addition we survey recent results analyzing the arithmetic quantifier structure of computational problems.
Free Games over Coloured Automata
Authors: Wiweger Antoni
Published: May 2021

Concepts of category theory are applied to the investigation of some relations between automata and abstract games. The notion of a coloured automaton introduced in this paper provides a framework for a unified treatment of automata and abstract games. Both games and automata can be viewed as special cases of this general notion. A coloured automaton is defined to be a Mealy automaton with the additional structure of a coloured graph on the set of inputs. Various categories of coloured automata, automata, and games are described. It is shown that some forgetful functors between these categories have left adjoints, and explicit constructions of these adjoints are given. The main result is Theorem 5.5 which describes a construction of a free abstract game over a coloured automaton satisfying some additional conditions.
On Enumerated Algebras and Some Monads in the Category of Enumerated Sets
Authors: Orlicki Andrzej
Published: May 2021

In this paper we investigate some properties of categories of enumerated algebras. In section 1 we prove that in case of the category of enumerated algebras satisfying some fixed set of identities, the forgetful functor into the category of enumerated sets is monadic. Then in sections 2 and 3 some applications of this result are presented. In particular, we show (see Theorem 3.2, section 3) that each finitary monad in the category of denumerable sets has a lifting to a monad in the category of enumerated sets.
Two Streamlined Depth-First Search Algorithms
Authors: Tarjan Robert Endre
Published: May 2021

Many linear-time graph algorithms using depth-first search have been invented. We propose simplified versions of two such algorithms, for computing a bipolar orientation or st-numbering of an undirected graph and for finding all feedback vertices of a directed graph.
Syntax and Defining Equations for an Interrupt Mechanism in Process Algebra1
Authors: Baeten J.C.M. , Bergstra J.A. , Klop J.W.
Published: May 2021

A mechanism is introduced to describe priorities in ACP, the algebra of communicating processes, whereby some actions have priority over others in a non-deterministic choice (or sum). This mechanism can be used to model the working of interrupts in a distributed system. This is illustrated in an extensive example.
On the Complexity of Deadlock Recovery
Authors: Leung Joseph Y.-T. , Monien Burkhard
Published: May 2021

We consider the computational complexity of finding an optimal deadlock recovery. It is known that for an arbitrary number of resource types the problem is NP-hard even when the total cost of deadlocked jobs and the total number of resource units are “small” relative to the number of deadlocked jobs. It is also known that for one resource type the problem is NP-hard when the total cost of deadlocked jobs and the total number of resource units are “large” relative to the number of deadlocked jobs. In this paper we show that for one resource type the problem is solvable in polynomial time when the total cost of deadlocked jobs or the total number of resource units is “small” relative to the number of deadlocked jobs. For fixed m ⩾ 2 resource types, we show that the problem is solvable in polynomial time when the total number of resource units is “small” relative to the number of deadlocked jobs. On the other hand, when the total number of resource units is “large”, the problem becomes NP-hard even when the total cost of deadlocked jobs is “small” relative to the number of deadlocked jobs. The results in the paper, together with previous known ones, give a complete delineation of the complexity of this problem under various assumptions of the input parameters.
Notions of Realizable Non-Sequential Processes
Authors: Fernandez C. , Nielsen M. , Thiagarajan P.S.
Published: May 2021

This paper presents some results on non-sequential processes using the language of net theory. The results are concerned with the relationship between various formalizations of the intuition that the causality relation enforced by a process should be in some sense “finitely realizable”. The formalizations proposed are of very different flavours, based on notions of observability, approximability, state space covering and discreteness.
Algebraic Approach to Database Constraints1
Authors: Orlowska Ewa
Published: May 2021

Algebraic methods of proving database constraints are proposed. The first method is based on the formulation of constraints in terms of inclusions of some binary relations associated with database. The relations are generated by indiscernibility relations by means of the operations of the algebra of binary relations. The second method is based on the matrix representation of constraints.
Decomposition of Transformation Groups of Permutation Machines
Authors: Niemenmaa Markku
Published: May 2021

By a permutation machine we mean a triple (Q,S,F), where Q and S are finite sets and F is a function Q × S → Q which defines a permutation on Q for every element from S. These permutations generate a permutation group G and by considering the structure of G we can obtain efficient ways to decompose the transformation group (Q,G). In this paper we first consider the situation where G is half-transitive and after this we show how to use our result in the general non-transitive case.
Preemptive Scheduling for Two-Processor Systems
Authors: Rowicki Andrzej
Published: May 2021

The purpose of the paper is to consider an algorithm for preemptive scheduling for two-processor systems with identical processors. Computations submitted to the systems are composed of dependent tasks with arbitrary execution times and contain no loops and have only one output. We assume that preemptions times are completely unconstrained, and preemptions consume no time. Moreover, the algorithm determines the total execution time of the computation. It has been proved that this algorithm is optimal, that is, the total execution time of the computation (schedule length) is minimized.
Free Net Algebras in VLSI-Theory
Authors: Molitor Paul
Published: May 2021

We provide a simple and uniform calculus of networks which allows us to treat both functional and structural properties of the circuits. By factorizing the algebras according to suitable relations, we obtain representations of integrated circuits on different design levels. With that, we give complete characterizations of these levels, i.e., expressions describing the same net with respect to a certain level can be transformed into each other by applying the corresponding rules.
On Correctness of Decision Algorithms in Information Systems
Authors: Wasilewska Anita
Published: May 2021

The concept of an information system, with manipulation based on the rough set theory, was introduced by Pawlak in 1982. The information system is defined by its set of objects, set of attributes, set of values of attributes, and a function, which maps the direct product of the first two sets onto the set of values of attributes. We introduce here, after [Pawlak 1985(1)], concepts of the decision rule, decision algorithm, static learning and describe the automatic procedures of deciding whether a given decision rule or decision algorithm is correct.
The Algebra of Synchronous Processes
Authors: Weijland W.P.
Published: May 2021

An algebraical theory called ASP is presented, describing synchronous cooperation of processes. The theory ASP was first mentioned in BERGSTRA & KLOP [4] as an alternative for the theory ACP, which works with asynchronous cooperation (see also in [5]). One of the main differences between ASP, as it is presented here, and the algebraic theory SCCS of MILNER [9] is the representation of parallelism, which is done by considering a computation step as a vector, each component of which represents an atomic action on a corresponding channel. This paper concludes with an example, to give an idea how to work with ASP.
Decidability of Formulas in Graph Theory
Authors: Moser Louise E.
Published: May 2021

A decision procedure is given for determining the validity of unquantified formulas in graph theory. The procedure, which decides equality and containment relations for vertex, edge, and graph terms, reduces to a decision procedure for propositional calculus. The correctness of the procedure is proved using model theory based on the axioms for graph theory provided. The complexity of the algorithm and its limitations are discussed.
On the λ Definable Higher Order Boolean Operations
Authors: Zaionc Marek
Published: May 2021

The purpose of this work is to show the methods of representing higher order boolean functionals in the simple typed λ calculus. In the paper is presented an algorithm for construction the λ representation of a functional given by generalized truth table. This technique is useful especially in functional programming languages such as ML in which functionals are expressed in the form of typed λ terms. Also λ representability of higher order functionals in many valued logics is discussed.
Abstraction and Empty Process in Process Algebra1
Authors: Baeten J.C.M. , Van Glabbeek R.J.
Published: May 2021

In this paper, we combine the hidden step η of the authors’ paper [2] with the empty process ε of VRANCKEN [12] and the authors’ [3]. We formulate a system ACPc, which is a conservative extension of the systems ACPη, ACP√, but also of ACPτ. This is a general system, in which most relevant issues can be discussed. Abstraction from internal steps can be achieved in two ways, in two stages: we can abstract to the hidden step η, and then from η to Milner’s silent step τ.
Stable Theories in Autoepistemic Logic
Authors: Marek W.
Published: May 2021

We investigate the operator producing a stable theory out of its objective part (A stable theory is a set of beliefs of a rational agent). We characterize the objective parts of stable theories. Finally, we discuss the predicate calculus case.
On Downward Closure Ordinals of Logic Programs
Authors: Bagai Rajiv , Bezem Marc , van Emden M.H.
Published: May 2021

Blair has shown that for every ordinal up to and including the least non-recursive ordinal there exists a logic program having that ordinal as downward closure ordinal. However, given such an ordinal and Blair’s proof, it is not straightforward to find a corresponding logic program. In fact, in the literature only a few isolated, ad hoc, examples of logic programs with downward closure ordinal greater than w can be found. We contribute to bridging the gap between what is known abstractly and what is known concretely by showing the connection between some of the existing examples and the well-known concept of the order of a vertex in a graph. Using this connection as a basis, we construct a family { P α } α < ϵ 0 of logic programs where any member P α has downward closure ordinal ω + α.
Towards a New Algebraic Foundation of Flowchart Scheme Theory
Authors: Căzănescu Virgil Emil , Ştefănescu Gheorghe
Published: May 2021

We develope a formalism for the algebraic study of flowchart schemes and their behaviours, based on a new axiomatic looping operation, called feedback. This formalism is based on certain flownomial expressions. Such an expression is built up from two types of atomic schemes (i.e., elements in a double-ranked set X considered as unknown computation processes, and elements in a “theory” T considered as known computation processes) by using three operations: sum, composition, and feedback. Flownomial expressions are subject to certain rules of identification. The axiomatization of flowchart schemes is based on the fact that a flowchart scheme may be identified with a class of isomorphic flownomial expressions in normal form. The corresponding algebra for flowchart schemes is called biflow. This axiomatization is extended to certain types of behaviour. We present axiomatizations for accessible flowchart schemes, reduced flowchart schemes, minimal flowchart schemes with respect to the input behaviour, minimal flowchart schemes with respect to the input-output behaviour etc. Some results are new, others are simple translations in terms of feedback of previous results obtained by using Elgot’s iteration or Kleene’s repetition. The paper also contains some historical comments.
Y-Logic: A Framework for Reasoning About Chameleonic Programs with Inconsistent Completions
Authors: Subrahmanian V.S.
Published: May 2021

Large logic programs are normally designed by teams of individuals, each of whom designs a subprogram. While each of these subprograms may have consistent completions, the logic program obtained by taking the union of these subprograms may not. However, the resulting program still serves a useful purpose, for a (possibly) very large subset of it still has a consistent completion. We argue that “small” inconsistencies may cause a logic program to have no models (in the traditional sense), even though it still serves some useful purpose. A semantics is developed in this paper for general logic programs which ascribes a very reasonable meaning to general logic programs irrespective of whether they have consistent (in the classical logic sense) completions.
Applications of Finite Models Properties in Approximation and Algorithmic Logics
Authors: Stepaniuk Jarosław
Published: May 2021

The purpose of this paper is to investigate some aspects concerning elementary theories of finite models and to give the applications in approximation logics and algorithmic theory of dictionaries.
A Compositional Semantics for Unmarked Predicate/Transition Nets1
Authors: Maggiolo Schettini Andrea , Pinna G. Michele , Winkowski Józef
Published: May 2021

Predicate/Transition nets are a high level description tool for complex systems. The paper aims at developing a semantics for Unmarked Predicate/Transition nets. This semantics, based on the concept of behavior as isomorphic class of unfoldings of the net, is compositional, i.e. the behavior of a complex net can be obtained by a suitable composition of the behaviors of its parts. The concept of behavior introduced here is similar to that of process for which an algebra has been developed in [16]. A case in which the behavior of Marked Predicate/Transition nets can be derived from the behaviors of its parts is also discussed.
A Uniform Test Approach for RCC-Adders1
Authors: Becker Bernd , Sparmann Uwe
Published: May 2021

In this paper testability aspects of Recursive Carry Computation adders are considered. The class of RCC-adders has been introduced in [5] and contains a wide range of different adder realizations (e.g., optimal time adders such as the the carry look-ahead adder of [8] and the conditional carry adder of [5]). We show that symbolic computation can be used to define this class and at the same time offers a uniform test approach which can be applied at an early stage of the design process. The class of RCC-adders itself splits into several subclasses which are specified by structural properties of the overall computation scheme and functional properties of the basic cells. Optimal complete test sets with respect to two commonly used fault models, the single stuck-at fault model and the single cellular fault model, are developed for these RCC-subclasses. The cardinality of the test sets depends on the choice of the fault model and on structural properties of the RCC-subclass. To summarize our results, we finally obtain tables with upper and lower bounds characterizing the test complexity of classes of RCC-adders. The upper bounds are obtained by the effective construction of complete test sets. The cardinality of these sets varies between a logarithmic or linear number of patterns for an n-bit RCC-adder.
About Semantic Action Refinement
Authors: Darondeau Philippe , Degano Pierpaolo
Published: May 2021

A notion of semantic action refinement is defined both on Synchronization Trees and on Causal Trees, a class of trees recently devised for giving a full account to causality [DD89]. The branching bisimulation, as introduced in [GW89a], is shown to be preserved under semantic action refinement. As a by-product, the axiomatization of the congruence induced by branching bisimulation which was given in [GW89a] is still valid under action refinement. Both results hold for Synchronization Trees and, with the needed extensions, for Causal Trees.
A Hierarchy of Context-Free Derivations
Authors: Mäkinen Erkki
Published: May 2021

This note discusses a hierarchy of different kind of context-free derivations by studying the corresponding Szilard languages. Especially, we introduce the leftmost and rightmost breadth-first derivations which are the counterparts of the well-known (depth-first) leftmost and rightmost derivations. It is shown that the Szilard languages related to different derivation types can be recognized by one-state automata which differ from each others by their memory devices.