bluuebunny/crossref_metadata_2025 huggingface dataset:
Time series analysis of computer network traffic in a dedicated link aggregation
Authors: Millán Ginno
Published: May 2021

Fractal behavior and long-range dependence are widely observed in measurements and characterization of traffic flow in high-speed computer networks of different technologies and coverage levels. This paper presents the results obtained when applying fractal analysis techniques on a time series obtained from traffic captures coming from an application server connected to the Internet through a high-speed link. The results obtained show that traffic flow in the dedicated high-speed network link have fractal behavior when the Hurst exponent is in the range of 0.5, 1, the fractal dimension between 1, 1.5, and the correlation coefficient between –0.5, 0. Based on these results, it is ideal to characterize both the singularities of the traffic and its impulsiveness during a fractal analysis of temporal scales. Finally, based on the results of the time series analyses, the fact that the traffic flows of current computer networks exhibit fractal behavior with a long-range dependency is reaffirmed.
Estimation of Global Solar Radiation on Horizontal Surfaces using Temperature-Based Model in Ilorin, Nigeria
Authors: ADEDIJI YAQUB BABATUNDE , Bamigboye Ayobami , Aboderin Joel Oluwaremilekun , Lekwa Onyeije Allison , Uzim Emmanuel Onyedikachi
Published: May 2021

In this study, the Solar Irradiation received was estimated in Illorin, Kwara, Nigeria, using the maximum and minimum temperature measured by an Arduino-based solar power parameter measuring system. The Extraterrestrial, Global and Diffuse Solar Radiation were estimated monthly using the Hargreaves and Samani model. This model also required the daily temperature, clearness index, and extraterrestrial solar irradiation in its use alongside the maximum and minimum temperatures. In using this model, we resolved the graphs of the three types of Solar Irradiation over ten days. For the selected days, the estimated extraterrestrial solar irradiation varies from 10.41kWh/m2 to 10.47 kWh/m2, while the mean extraterrestrial solar irradiation is 10.44 kWh/m2. The estimated global solar irradiation varies from 4.42 kWh/m2 to 5.677kWh/m2, while the estimated mean global solar irradiation is 5.19kWh/m2 per day. The estimated diffuse solar irradiation varies from 3.46kWh/m2 to 5.48kWh/m2, while the mean diffuse solar irradiation is per day is 4.61kWh/m2.
Experimental Investigation and Numerical Modeling of Piezoelectric Bender Element Motion and Wave Propagation Analysis in Soils
Authors: Liu Hongwei , Cascante Giovanni , Maghoul Pooneh , Shalaby Ahmed
Published: May 2021

The bender element (BE) test has been widely used for the characterization of soil specimens to determine the dynamic or low-strain shear modulus. However, the actual behavior of the BE inside the soil specimen still remains unknown. The current ASTM standard does not consider the interference of P waves in BE measurements, which can lead to significant errors in the evaluation of shear wave velocities. In this paper, the BE motion inside different media is numerically studied through a coupled piezoelectric and solid mechanics finite element (FE) model. The numerical results are calibrated and compared with the real motion of the BE monitored using a high-frequency laser vibrometer. The proposed model successfully captured the measured motion of the BE in the air as well as transparent soils.More importantly, the proposed model provided a method for understating the interactions of P waves and S waves in a soil specimen. Simulated signals for an Ottawa sand specimen showed a good agreement with independent results from resonant column tests. The proposed piezoelectric-solid mechanics FE model can be used to study the soil-bender element interaction so that sound recommendations can be given to improve the interpretation of BE tests for different soils.
Advances in Bianisotropic GSTC-based Metasurfaces
Authors: Lavigne Guillaume , Caloz Christophe
Published: May 2021

We present an overview of some of our recent advances on bianisotropic metasurfaces synthesized using susceptibility-based General Sheet Transition Conditions (GSTCs). Specifically, we discuss a series of related applications, which highlight the versatility and power of this method.
Consensus (Hard Fork) PoST Datastore for Advanced Cryptography and Higher Efficiency Mining
Authors: Kamal Andrew
Published: May 2021

This BIP aims to provide a more complex cryptography alternative to Bitcoin's traditional encryption scheme. Secondly, it also specifies a hybrid algorithm for allowing for both traditional PoW and memory hard mining. The aim is for more optimal cryptographic efficiency and sustainable security in the future.
Personality Disorder and Verbal Behavior
Authors: Entwistle Charlotte , Marceau Ely , Boyd Ryan L.
Published: May 2021

Today, the development of new technologies means that there are many advanced tools that can be used to improve our understanding of personality disorder, and, in turn, the treatment of personality disorder. One particularly promising tool — indeed, the focus of this chapter — is computerized language analysis. Through the exploration and analysis of verbal behavior, it is possible to empirically develop new insights into personality disorder, broadly defined. That is, by looking at patterns in the way that people with personality disorder use language — the words that they use and the way in which they use them — we can gain access into their broad constellation of thinking, feelings, and behaviors, as well as how precisely each of these features contributes to their pathology.To date, however, there has been very little research at the intersection of verbal behavior and personality pathology. Accordingly, the goal of this chapter is to describe and discuss how personality disorder may become better understood through the application of natural language analysis, providing a rough roadmap for the development of personality disorder studies using modern methods. Specifically, in this chapter we will provide:1. A brief background and overview of personality disorder;2. An overview of how natural language processing (NLP) methods have advanced understanding within the wider field of psychology, focusing on personality psychology and psychopathology specifically; 3. Examples that demonstrate how NLP methods can help to resolve some of the fundamental, unanswered questions and debates in the personality disorder literature.
Correlation analysis to investigate unconscious mental processes: A critical appraisal and mini-tutorial
Authors: Malejka Simone , Vadillo Miguel A. , Dienes Zoltan , Shanks David
Published: May 2021

As a method to investigate the scope of unconscious mental processes, researchers frequently obtain concurrent measures of task performance and stimulus awareness across participants. Even though both measures might be significantly greater than zero, the correlation between them might not, encouraging the inference that an unconscious process drives task performance. We highlight the pitfalls of this null-correlation approach and provide a mini-tutorial on ways to avoid them. As reference, we use a recent study by Salvador, Berkovitch, Vinckier, Cohen, Naccache, Dehaene, and Gaillard (2018) reporting a non-significant correlation between the extent to which memory was suppressed by a Think/No-Think cue and an index of cue awareness. In the Null Hypothesis Significance Testing (NHST) framework, it is inappropriate to interpret failure to reject the null hypothesis (i.e., correlation = 0) as evidence for the null. Furthermore, psychological measures are often unreliable, which can dramatically attenuate the size of observed correlations. A Bayesian approach can circumvent both problems and compare the extent to which the data provide evidence for the null versus the alternative hypothesis (i.e., correlation > 0), while considering the usually low reliabilities of the variables. Applied to Salvador et al.’s data, this approach indicates no to moderate support for the claimed unconscious nature of participants’ memory-suppression performance—depending on the model of the alternative hypothesis. Hence, more reliable data are needed. When analyzing correlational data, we recommend researchers to employ the Bayesian methods developed here (and made freely available as R scripts), rather than standard NHST methods, to take account of unreliability.
Characteristics of smartphone-based dietary assessment tools: A systematic review
Authors: König Laura M , Van Emmenis Miranda , Nurmi Johanna , Kassavou Katerina , Sutton Stephen
Published: May 2021

Smartphones have become popular in assessing eating behaviour in real-life and real-time. This systematic review provides a comprehensive overview of smartphone-based dietary assessment tools, focusing on how dietary data is assessed and its completeness ensured. Seven databases from behavioural, social and computer science were searched in March 2020. All observational, experimental or intervention studies and study protocols using a smartphone-based assessment tool for dietary intake were included if they reported data collected by adults and were published in English. Out of 21,722 records initially screened, 117 publications using 129 tools were included. Five core assessment features were identified: photo-based assessment (48.8% of tools), assessed serving/ portion sizes (48.8%), free-text descriptions of food intake (42.6%), food databases (30.2%), and classification systems (27.9%). On average, a tool used two features. The majority of studies did not implement any features to improve completeness of the records. This review provides a comprehensive overview and framework of smartphone-based dietary assessment tools to help researchers identify suitable assessment tools for their studies. Future research needs to address the potential impact of specific dietary assessment methods on data quality and participants’ willingness to record their behaviour to ultimately improve the quality of smartphone-based dietary assessment for health research.
46, XY Disorder of Sexual Development with Ambiguous Female External Genitalia: A Case Report
Authors: Sah Anil Kumar , Maharjan Bipin , Adhikari Mahesh Bahadur , Baral Suman , Giri Mimi
Published: May 2021

Disorder of Sexual Development (DSD) is a group of congenital conditions with atypical development of sex at chromosomal, gonadal or anatomic level. Genetic males with DSD (46 XY DSD) can present with female external genital phenotype, ambiguous, or a micropenis. It is caused by incomplete intrauterine masculinization with or without the presence of Müllerian structures. It results either from decreased synthesis of testosterone or DHT or from impairment of androgen action. Herein, we report a case of a 13-year child raised as female with hoarseness of voice and gradual enlargement of clitoris with hormonal assessment not suggestive of either 5 Alfa Reductase deficiency, Congenital Adrenal Insufficiency Syndrome or 17β-Hydroxysteroid Dehydrogenase deficiency
IMPACTOS TÉCNICO-ECONÔMICOS DA ADUBAÇÃO DE PASTOS
Authors: Avelino Cabral Carlos Eduardo , Cabral Carla Heloisa Avelino , Santos Alyce Raiana Monteiro , Motta Aline Müller , Mota Lucas Gimenes
Published: May 2021

A criação de bovinos no Brasil ocorre, prioritariamente, em pastagens e, neste contexto, a adubação do pasto é uma importante estratégia de aumento na eficiência produtiva. Diante disso, objetivou-se, com esta revisão, descrever os impactos técnicos da adubação no desenvolvimento de gramíneas tropicais. A calagem é uma prática importante na disponibilidade dos nutrientes e, novos estudos visam demonstrar que o intervalo entre a incorporação do calcário e a semeadura tem maior dependência da umidade do solo e que é possível reduzir este período que tradicionalmente é de 60 a 90 dias. A adubação fosfatada tem maior impacto sobre a implantação do que a manutenção do pasto, e quando negligenciada na formação do pasto, observa-se um efeito residual sobre a rebrota. O nitrogênio e o potássio são os nutrientes mais extraídos na manutenção dos pastos, o que se torna importante o estudo da relação entre estes nutrientes, bem como a adoção da adubação potássica em sistemas em que a adubação nitrogenada é uma prática rotineira. A varredura, que consiste na mistura de sobras de fertilizantes em galpões, embora tenha baixo custo por quilo de produto, o uso pode ser antieconômico, o que depende da composição do insumo adquirido.
Palavras-chave: calagem; fertilização de pastos; formação de pastagens.
 
Technical and economic impacts of pasture fertilization
 
ABSTRACT: Cattle production on Brazil priority occurs in grasslands, in this context, pasture fertilization is an important strategy to improve production efficiency. Therefore, the aim with this review is to describe the technical impacts of fertilization on tropical grass development. Liming is an important practice in nutrient availability and new studies aim to demonstrate that the interval between limestone incorporation and seeding has more dependence on soil moisture, and that is possible to reduce this period, which traditionally is from 60 to 90 days. Phosphate fertilization has a greater impact on pasture implantation than maintenance, and when neglected in pasture formation, there is a residual effect on regrowth. Nitrogen and potassium are the nutrients extracted on pasture maintenance, which makes it important to study the relationship between these nutrients, as well as the adoption of potassium fertilization in systems where nitrogen fertilization is a routine practice. Mixing leftover fertilizers in warehouses, although it has a low cost per kilo of product, the use can be uneconomical, which depends on the input composition purchased.
Keywords: liming; pasture fertilization; pasture implantation.
Factors Affecting the Capacity of Accounting Software in Controlling Frauds and Errors in Small and Medium Enterprises (Smes): A Case Study of SMEs in Hanoi, Vietnam
Authors: Hang Ngo Thi Thu , Hai Vu Thi , Trung Tran Quang , Chien Vu Manh , Nga Nguyen Thi Hong
Published: May 2021

Financial accounting information has impacted the operation of enterprises, especially SMEs. With the development of technology, digital accounting applications are playing an increasingly important role in minimizing mistakes, and ensuring the accuracy and timeliness of accounting information. Using multiple discriminant analyses, this study confirmed the significance of accounting software in reducing frauds and errors in SMEs’ businesses despite some drawbacks. It showed that the managers’ ability to access the software and the decentralization of power in accessing the  accounting software were the two key factors deciding the success/failure of applying accounting software to control frauds and errors. In addition, smart applications of the accounting software positively contributed to the elimination of frauds in enterprises. Based on these results, recommendations are drawn for SMEs, such as investing more in smart applications of accounting software, as well as updating knowledge about accounting for management, in order to get more advantages from accounting software applications for their business in the long term.
Effect of Plant Density and Hand Weeding on Weed Control and Yield of the Vegetable Corn
Authors: Tran Thiem Thi , Thu Thieu Thi Phong , Loan Nguyen Thi
Published: May 2021

Weed infestation has an adverse impact on the yield of vegetable corn. This study, therefore, aimed to investigate the effects of plant density and hand weeding on controlling weeds and yield of vegetable corn. The experiments were conducted in the field condition in a randomized complete block design with three replications. The planting densities were 79,365 plants ha-1 (D1); 92,593 plants ha-1 (D2); 111,111 plants ha-1 (D3); and 138,889 plants ha-1 (D4). The hand weeding treatments were no weeding (NW), hand weeding once at 3-4 leaf stage of vegetable corn (HW1), and hand weeding twice at 3-4 leaf and 8-9 leaf stages of vegetable corn (HW2). The results showed that the highest planting density combined with hand weeding was generally effective in controlling weeds. Furthermore, the increase in planting density combined with hand weeding significantly improved the physiological traits, which consequently increased the cob yield. The yield was optimum at D3 combined with hand weeding once. Thus, the results suggested that the optimum yield of vegetable corn could be obtained at a planting density of 111,111 plants ha-1 combined with hand weeding once at 3-4 leaf stage, an increase of the cob yield by 2.01 tons ha-1.
An investigation on the effect of cutting parameters in CNC plasma cutting process for carbon steel
Authors: Hang Pham Thi , Chau Nguyen Thi , Khang An Duong , Anh Nguyen Hoang , Son Pham Hong
Published: May 2021

The effect of technological parameters such as gas pressure, cutting current, standoff distance, and cutting speed on the cutting surface quality of CNC plasma cutting process was investigated. The experiment was carried out by Bruco CNC plasma cutting machine for CT3 steel with different thicknesses. The quality characteristics examined included the ability to cut out samples, the slag formation on the surface, the surface roughness, and the cut angle. The analysis of the results was made using the Taguchi method in order to determine the contribution of each-individual parameter to the cutting quality, especially surface roughness. The obtained results show that the value of cutting current should be set up at a real value in order to cut out of the sample. The air pressure strongly affected the slag formation. The surface roughness was mainly affected by the standoff distance and air pressure, whereas the cutting speed and cutting current were the minor influencing parameters.
Production Efficiency Analysis of Indigenous Pig Production in Northwest Vietnam
Authors: Tuan Tran Ba , Yin Tong , Cuong Tran Huu , Tiep Nguyen Cong , König Sven
Published: May 2021

This research was conducted to investigate the production efficiency of Ban pig production in northwest Vietnam between October 2016 and January 2017. Primary data obtained from 171 producers were analyzed by applying cost-benefit analysis and stochastic frontier production function. The benefit-cost ratio per litter was 1.24, indicating that the enterprise was profitable. Compared to other farms, the farms focused on farrow-to-finisher attained the highest net return (EUR 213.71/litter), while inputs were used most effectively by the mixed farms. The results from the Cobb-Douglas production function revealed that labour, feeding costs, stocking density, and pigpen structure had positive effects on the production output. Additionally, farms with the phase of farrow-to-nursery obtained less total revenue, while farms focused on the farrow-to-finisher phase achieved higher production outputs than the mixed farms. The level of technical efficiency for each farm ranged between 0.62 and 0.98, with a mean of 0.88. The number of live-born piglets and depreciation cost had positive effects, whereas the nursery interval had a negative impact on the technical efficiency. Ban pig producers could increase technical efficiency by efficiently utilizing available resources and improving managerial skills.
ANALYSIS OF FINITE ELEMENT SOLUTION CONSERVATIVE SMOOTHING INFLUENCE ON THE ZERO ENERGY MODES SUPPRESSION
Authors: Kibets A.I. , Bezhentseva M.V.
Published: May 2021

The problem of high-speed penetration of a non-deformable cylinder into a steel plate is considered. The defining system of equations is formulated in Lagrange variables in a three-dimensional formulation. The equation of motion is derived from virtual work capacities balance. Kinematic relations are recorded in the metric of the current state. The relations of the flow theory with kinematic and isotropic hardening are used as equations of state. The contact interaction of the cylinder and the plate is modeled by non-penetration conditions. The numerical solution of the problem under given boundary and initial conditions is based on the moment scheme of the finite element method and “cross” type explicit time integration scheme. To discretize the defining system of equations with respect to spatial variables, 8-node isoparametric finite elements with multilinear form functions are used. To suppress the high-frequency oscillations of the numerical solution, the procedure of nodal displacement velocities conservative smoothing is used. The smoothing algorithm is based on the momentum conservation law, focused on finite element grids consisting of blocks that are mutually unambiguously mapped to a unit cube. To analyze the nodal displacement velocities monotonicity, the numerical solution splitting in the directions of the finite element grid lines is used. As the results of computer modeling have shown, the finite elements of the plate are exposed large deformations and rotation angles as a rigid whole during local intense dynamic loading. The conservative smoothing procedure influence on the numerical solution stability is analyzed. It is shown that in the problem under consideration, without applying the conservative smoothing procedure, zero-energy modes develop in the contact zone in the finite-element grid of the plate (an hourglass-type instability) and the collision process cannot be modeled before the cylinder rebounds.
Algorithmic logic and its applications in the theory of programs I
Authors: Mirkowska Grażyna
Published: May 2021

The paper presents tools for formalizing and proving properties of programs. The language of algorithmic logic constitutes an extension of a programming language by formulas that describe algorithmic properties. The paper contains two axiomatizations of algorithmic logic, which are complete. It can be proved that every valid algorithmic property possesses a formal proof. An analogue of Herbrand theorem and a theorem on the normal form of a program are proved. Results of meta-mathematical character are applied to theory of programs, e.g. Paterson’s theorem is an immediate corollary to Herbrand’s theorem.
A natural method of proving properties of programs
Authors: Winkowski Jozef
Published: May 2021

In this paper an approach to proving properties of programs is presented, which slightly differs from the methods developed up to now. In contrast to other approaches it needs no formal program notion but only a formalization of some basic program properties. The key idea in this approach is to associate with any program under consideration a formal theory in such a way that all the processes, which may be thougth as possible executions of the program considered, become models of the associated theory. Such a theory can be constructed by formulating axioms about the program executions, and about quantities which explicitly or implicitly occur in the program and change their values while the program is being executed. Appropriate axioms and the properties which are to be proved can easily be described by formulas of the predicate logic. This enables one to consider various properties of the program as theorems of the resulting theory and to prove them by usual means of the predicate logic.
On maximal parallel realization of processes
Authors: Dembiński Piotr
Published: May 2021

A simple (finite automata) model for parallel computation is considered. The parallelism is replaced by nondeterminism. The class of all parallel realizations of given processes is algebraically characterized, and a natural “less parallel” gelation between realizations is introduced. A sufficient and necessary condition is riven for the existence of the maximally parallel realization in the set of correct lealizations (distinguished by means of computational invariants).
Stochastic informational systems I
Authors: Marek Wiktor , Traczyk Tadeusz
Published: May 2021

In the paper the notion of a stochastic informational retrieval system is introduced and discussed. This is a generalization of the notion of an i.s.r. system in the case of data which are measured with some precision. The method of numerical Boolean algebras is applied. Theorems connected with the decomposition of such systems are proved.
An algebraic approach to the theory of recursive coroutines
Authors: Janicki Ryszard
Published: May 2021

A mathematical model for recursive coroutines in introduced. Relationships between Mazurkiewicz algorithms and this model are considered. Some linguistic and computational properties of coroutines are proved. The set of all functions computed by programs with recursive coroutines is proved to contain the set of all functions computed by commonly used recursive programs.
Sets of sequences constructed by nondeterministic k-machines and deterministic k-machines
Authors: Karásek Jiří
Published: May 2021

The paper deals with nondeterministic and deterministic k-machines which represent, in a certain sense, generalizations of some well-known notions. Connections between the sets of sequences constructed by nondeterministic and deterministic k-machines, and some other related problems are investigated.
PPC (Pisa Proof Checker): a tool for experiments in theory of proving and mathematical theory of computation
Authors: Aiello Luigia , Aiello Mario , Attardi Giuseppe , Prini Gianfranco
Published: May 2021

An interactive proof checker is a system which is able of building a formal proof (in some deductive calculus) by executing commands provided by the user. Proof checkers are useful both for making experiments in proof construction within various formal systems and for proving theorems in those fields of mathematics (such as mathematical theory of computation) where proofs are necessarily very large and unfeasible by hand. Two levels may be distinguished in a proof checker. The lower one implements the proof management routines, and is independent of any particular logic. The higher one implements the inference rules of a particular logical calculus. Powerful higher level rules are also needed to make the use of the checker practical. Almost all routine steps may be then generated automatically, and the user has just to give some “hints” to the checker, which transforms an “informal argument” into a formal proof.
Continuous informational systems
Authors: Konikowska Beata
Published: May 2021

A continuous information (c.i.) system is an informational system in which every object is described by a vector of functions of real variable. In the special case where all these functions are constant the c.i. system is equivalent to the information storage and retrieval (i.s.r.) system defined by Marek and Pawlak in [3]. The paper deals with a description language for a c.i. system. The structure of this language is analogous to the structure of the description language for i.s.r. systems introduced in [3]. Terms represent properties of objects, and formulas are statements about the system. All terms are built by means of Boolean operations from terms representing properties of the type (ajx)(I) ⊂ A, where ajx is the jth function describing the object x, I is an open interval or a point of the real line, and A is an arbitrary subset of the codomain of ajx. The axioms for the description language together with an inference rule are given. The valuation of terms and formulas is defined and the adequacy theorem is proved. Basing on a certain normal form theorem and the properties of a special system Smax, the completeness theorem is finally proved.
Programmability and P = N P conjecture
Authors: Radziszowski Stanisław
Published: May 2021

We define the time-complexity of programs (FS-expressions) in an arbitrary relational system. We extend these notions to nondeterministic programs (NFS-expressions). There are some sufficient conditions for a relational system which ensure the equivalence of the P = N P problem in that system to the classical P = N P problem for Turing machines. This implies that the P = N P problem can be solved in thc theory of programs in some relational systems.
A formalism for describing non-sequential processes
Authors: Winkowski Józef
Published: May 2021

In the paper a formalism is suggested for describing non-sequential processes. Processes are defined in this formalism by finite sets of rules. Such sets, called algorithms, consist of rules which indicate how relations between occurring objects may change (in general concurrently). They constitute a language of algorithms. Mathematical semantics of two types are formulated for this language. Ones, called objective, give descriptions of executions of algorithms in terms of objects which really exist in these executions. Other, called subjective, offer descriptions from the point of view of an observer. It is shown that objective semantics can be modelled in subjective ones.
On the generation of prime implicants
Authors: Reusch Bernd , Detering Lothar
Published: May 2021

It is shown that various well-known normal forms for Boolean functions can be derived from a very general representation of subfunctions. Another general theorem on the relation between the prime implicants of a function and the prime implicants of its subfunctions is used to prove correct various methods of generating prime implicants.
On the structure of polynomially bounded DOL systems
Authors: Ehrenfeucht Andrzej , Rozenberg Grzegorz
Published: May 2021

A notion of a DOL system with rank is introduced. It provides a structural characterization of polynomially bounded DOL systemso Several consequences of such a characterization are studied.
Topological sorting and well-formed strings1
Authors: Meyers Wiliam James
Published: May 2021

A topological sorting of a tree is a linear ordering of its elements that preserves and extends their partial ordering in the tree. Any such arrangement of tree elements has a characteristic property, involving collective weights of initial or final substrings. Such properties have been investigated in connection with random walks, combinatorial arrangements, and the well-formed strings of parenthesis-free notations. Topological sortings of directed acyclic graphs exhibit a similar structure.
On an efficient method of information retrieval
Authors: Lipski Witold
Published: May 2021

A new method of organizing an information storage and retrieval system is proposed and theoretically evaluated. The method uses a special normal form into which the queries entering the system are transformed. This normal form enables one to determine easily the decomposition of the set of records relevant to a query into the minimal number of segments of records stored in consecutive storage locations, and to compute the addresses of the beginning and end of each of these segments.
Efficient outerplanarity testing
Authors: Sysło Maciej M. , Iri Masao
Published: May 2021

This paper describes an efficient algorithm for finding whether a graph G has an outerplanar embedding in the plane. The algorithm is a realization of an inductive characterization of outerplanar graphs and uses depth-first search for coding a structure of a graph which is represented by adjacency lists. The algorithm has O(V) time and space bounds, where V is the number of vertices in G.
Definability in algorithmic logic
Authors: Dańko Wiktor
Published: May 2021

In this paper we consider recursive implicit definitions of functors and predicates in algorithmic logic [1], [5], [9], which may be regarded as procedures (compare A. Salwicki [10]). We examine the possibility of elimination of defined symbols from algorithmic formulas. We prove that the halting property of a procedure is not definable by means of formulas of extended algorithmic logic [1] (with classical quantifiers). As corollary we obtain that extended algorithmic logic has not Beth-property.
Query language of stochastic information systems
Authors: Konikowska Beata , Traczyk Tadeusz
Published: May 2021

For a class of stochastic information systems a query language is defined and the completeness property proved. It is also shown that each term may be transformed into a canonical form, and in some special case into a normal additive form.
Model existence theorem in algorithmic logic with non-deterministic programs1
Authors: Mirkowska Grażyna
Published: May 2021

The paper is a continuation of the considerations connected with non-deterministic algorithmic logic. We will formulate a Hilbert style axiomatization basing on the analogous one defined for algorithmic logic. The main result is the theorem asserting that every consistent non-deterministic algorithmic theory possesses a model.
Complexity of index sets and translating functions
Authors: Leitsch Alexander
Published: May 2021

The connection between index stes appearing in recursive enumerations of subrecursive classes and translating functions is investigated. Referring to a construction, which yields enumerations with low complexity for some index sets, we show that in such a case the complexity for some translating functions must be high. Furthermore a class of enumerations is discussed, which has elementary translating functions, but an important part of the index sets is not decidable by algorithms of the enumerated class (these index sets are of the form { x : ψ x ( a ) = f ( x )}).
General theory of relational automata
Authors: Trnková Věra
Published: May 2021

General theory of relational automata, including non-deterministic linear and bilinear machines, structured non-deterministic tree automata and automata in some primitive classes of algebras, is developed. Particular attention is paid to languages accepted by finite relational automata.
Resolution systems and their applications I
Authors: Orłowska Ewa
Published: May 2021

The central method employed today for theorem-proving is the resolution method introduced by J. A. Robinson in 1965 for the classical predicate calculus. Since then many improvements of the resolution method have been made. On the other hand, treatment of automated theorem-proving techniques for non-classical logics has been started, in connection with applications of these logics in computer science. In this paper a generalization of a notion of the resolution principle is introduced and discussed. A certain class of first order logics is considered and deductive systems of these logics with a resolution principle as an inference rule are investigated. The necessary and sufficient conditions for the so-called resolution completeness of such systems are given. A generalized Herbrand property for a logic is defined and its connections with the resolution-completeness are presented. A class of binary resolution systems is investigated and a kind of a normal form for derivations in such systems is given. On the ground of the methods developed the resolution system for the classical predicate calculus is described and the resolution systems for some non-classical logics are outlined. A method of program synthesis based on the resolution system for the classical predicate calculus is presented. A notion of a resolution-interpretability of a logic L in another logic L ′ is introduced. The method of resolution-interpretability consists in establishing a relation between formulas of the logic L and some sets of formulas of the logic L ′ with the intention of using the resolution system for L ′ to prove theorems of L. It is shown how the method of resolution-interpretability can be used to prove decidability of sets of unsatisfiable formulas of a given logic.
Conjugated measures of computational complexity
Authors: Adrianopoli Faurto
Published: May 2021

It is shown here that using the Kleene’s normal form for partial recursive functions (p.r. functions) it is possible to develop a different normal form which will give a relation between these p.r. functions and certain related step-counting ones. Also this new form suggests an interesting serial expansion in terms of minimal functions of these p.r. functions. The notion of conjugated systems of computational complexity is eventually introduced.
On the algorithmic theory of stacks1
Authors: Salwicki Andrzej
Published: May 2021

The algorithmic theory of stacks, ATS, formalizes properties of relational systems of stacks. It turns out that apart from previously known axioms a new axiom of algorithmic nature, while ¬ empty (s) do s: = pop (s) true is in place. The representation theorem stating that every relational system of stacks is isomorphic to a system of finite sequences of elements is proved. The connections between ATS and a type STACKS declaration (written in LOGLAN programming language) are shown.
Incomplete information in a relational database
Authors: Grant John
Published: May 2021

In this paper we investigate the inclusion of incomplete information in the relational database model. This is done by allowing nonatomic entries, i.e. sets, as elements in the database. A nonatomic entry is interpreted as a set of possible elements, one of which is the correct one. We deal primarily with numerical entries where an allowed set is an interval, and character string entries. We discuss the various operations of the relational algebra as well as the notion of functional dependency for the database model.
NP-completeness of combinatorial problems with unary notation for integers
Authors: Penttonen Martti
Published: May 2021

Most NP-complete problems remain NP-complete even though the notation for integers is changed to unary. The knapsack problem is an exception, it becomes provably polynomial time recognizable. However, we present a modified knapsack problem that remains NP-complete also in unary notation.
Programs as term transformers
Authors: Sokołowski Stefan
Published: May 2021

Predicates describing the states of computation may be regarded as functions into the Boolean algebra {false, true} and programs as transformers of those functions. If we do not restrict ourselves to this algebra, we get instead terms describing the states of computation and programs transforming the terms. In many cases this approach turns out to be more natural. This paper is a mathematical study of partial correctness and termination of programs in the language of term transformations.
Decision problems in generalized vector addition systems
Authors: Büning Hans Kleine
Published: May 2021

This paper concerns with the reachability and equality problem of generalized vector addition systems, where the systems work in the cartesian-product of the integers with finite (resp. infinite) exception set.
Lattice Theoretic Ordering Properties for NP-Complete Optimization Problems
Authors: Ausiello Giorgio , d’Atri Alessandro , Protasi Marco
Published: May 2021

The ordering among classes of isomorphic NP-complete optimization problems is studied from a lattice theoretic point of view. It is shown that the set of such classes has the structure of an upper semilattice; while a top element can found be it is proved that no bottom element can exist.
On the Synchronizing Tools for Parallel Programs
Authors: Müldner Tomasz
Published: May 2021

The paper contains precise and structured definitions of the following synchronizing tools: Mutually Excluding Regions, Elementary Critical Regions and Critical Regions. Some applications of these tools are shown on the following examples: the Kung algorithm of finding a zero of a function, ticket booking system, and synchronous and asynchronous Jacobi algorithms of solving a system of linear equations. Next, the implementations of the above synchronizing tools in the formal languages of parallel programming are given. The semantics of these languages are defined on the ground of the present author’s earlier paper “On the Semantics of Parallel Programs”. The implementations are proved to be correct. The implementation of a critical region is actually an implementation of Dijkstra P and V operations on binary semaphores.
On Sub Regular OL Forms
Authors: Albert J. , Maurer H.A. , Ottmann Th.
Published: May 2021

We present necessary and sufficient conditions for an OL form F to generate regular languages only. The conditions at issue can be effectively checked, whence the “regularity problem for OL forms” is proven decidable.
On Universal Binary Search Trees
Authors: Fischer Thomas R.M.
Published: May 2021

The paper deals with the problem of constructing binary search trees that are available in the case of unknown or time varying access probabilities.
Algorithmic Aspects of the Attribute Set Minimization Problem
Authors: Truszczyński Mirosław
Published: May 2021

Algorithmic aspects of the problem of minimizing the set of attributes in an information system are considered. Two simplifications of this problem are proved to be NP-complete. A simple heuristic algorithm is presented and analyzed.
Generalized Inverse of a Finite Graph
Authors: Mrożek Marian
Published: May 2021

We define the optimal generalized inverse of the directed graph, give its construction and prove that the graph has an inverse graph iff its optimal generalized inverse is its inverse. The construction of the optimal generalized inverse may be used in the preparation of the PERT networks by the computer.
Algorithmic Triviality of Abstract Structures
Authors: Urzyczyn Paweł
Published: May 2021

In the present paper we investigate algorithmically trivial structures, that is structures where every recursive function (relation) is definable by a first-order open formula. We prove that algorithmic triviality is equivalent to a property called the unwind property. We also study the notion of effective interpretation of structures and its relation to algorithmic triviality.
On the Quantifier-Free Fragment of ‘Logic of Effective Definitions’
Authors: Bergstra Jan A. , Meyer John J.Ch.
Published: May 2021

In [2] Jerzy Tiuryn has introduced Logic of Effective Definitions (LED) in which properties of effective definitional schemes are expressed. With respect to the quantifier-free part of it, he proved that each open formula is equivalent to one in a special conjunctive normal form. We prove that there is no finite bound to the number of conjuncts required for these normal forms.
The Equational Specification of Finite Minimal Unoids Using only Unary Hidden Functions
Authors: Bergstra Jan A. , Meyer John-Jules Ch.
Published: May 2021

In [5] it has been proved that by using hidden functions the number of equations needed to specify a finite data type is bounded by numbers depending only on the signature of that data type. In the special case of a finite minimal unoid, however, it seems to be relevant to ask whether or not a specification can also be made by a bounded number of equations using only unary hidden functions. In this paper we prove that this can be done.
Elgot’s Analysis of Monadic Computation
Authors: Bloom Stephen L.
Published: May 2021

A review is given of some of the late C.C. Elgot’s ideas on the syntax and semantics of monadic flowchart algorithms. In particular, the motivation for his “iterative algebraic theories” is explained.
An Operator Precedence Parsing Algorithm
Authors: Fischetti Enrico , Smaldone Roberto
Published: May 2021

Operator precedence parsers suffer the disadvantage of parsing invalid as well valid strings. This problem is scrutinized in relation to previous papers of Henderson and Levy (3) and Williams (4) and a parsing algorithm is put forward, capable of parsing a large class of operator precedence grammars.
Complexity of Craig’s Interpolation
Authors: Mundici Daniele
Published: May 2021

In this paper we investigate the length ‖ χ ‖ of the shortest interpolant of a valid implication φ → ψ in terms of ‖ φ ‖ + ‖ ψ ‖, both in sentential and in first-order logic. In the case of sentential logic, we give a precise exponential upper bound for ‖ χ ‖. We also show that the information about the growth of ‖ χ ‖ has some implications for computation theory. In the case of first-order logic we exhibit a very short valid implication whose interpolants are all impossibly long.
Tree Rewriting Systems, Combinatory Weak Reduction Systems and Type Free Languages1
Authors: Pettorossi Alberto
Published: May 2021

In this paper we consider combinators as tree transducers: this approach is based on the one-to-one correspondence between terms of Combinatory Logic and trees, and on the fact that combinators may be considered as transformers of terms. Since combinators are terms themselves, we will deal with trees as objects to be transformed and tree transformers as well. Methods for defining and studying tree rewriting systems inside Combinatory Weak Reduction Systems and Weak Combinatory Logic are also analyzed and particular attention is devoted to the problem of finiteness and infinity of the generated tree languages (here defined). This implies the study of the termination of the rewriting process (i.e. reduction) for combinators.
Control of Petri Nets by Finite Automata
Authors: Burkhard Hans-Dieter
Published: May 2021

Petri nets are considered where the firings are controlled by finite automata. The control may be distributed to different automata working over disjoint sets of transitions. To avoid deadlocks and conflicts for the whole system the distribution of control must be organized in an appropriate manner. The existence of deadlocks and conflicts is shown to be undecidable in general, but conflict resolving and deadlock free controls can be constructed for given nets.
Interpretability of Algorithmic Theories
Authors: Dańko Wiktor
Published: May 2021

In this paper we consider interpretability between algorithmic theories, i.e., formalized theories based on the algorithmic Logic (cf. [1,3]). We adopt the notion of interpretability proposed by Szczerba (cf. [7,8]). We show that some facts true in the case of interpretability of first order theories are also true in the case of interpretability of algorithmic theories. We give examples of hereditary and nonhereditary properties of interpretability of algorithmic theories.
On Effective Numberings of Effective Definitional Schemes
Authors: Orlicki Andrzej
Published: May 2021

We try to define effective numberings of the logic of effective definitional schemes which has been defined in Tiuryn [4]. It turns out that a reasonable way of doing it leads us to the functions which are not surjective. Therefore in the traditional sense they are not effective numberings. However, these functions induce “good” numberings of the set of functions computable by effective definitional schemes.
Dependencies of Attributes in Pawlak’s Information Systems
Authors: Orłowska Ewa
Published: May 2021

In the paper we consider dependencies of attributes in Pawlak’s model of information systems. We develop a logic which enables us to express and to prove dependencies. We present a Gentzen-style deduction system for the logic.
An Interpretability Approach to the Theory of Abstract Data Types1
Authors: Dańko Wiktor
Published: May 2021

In this paper, similarly to [1,4,17,20,21,29,30], abstract data types are understood as formalized many-sorted theories based on algorithmic languages (e.g. a language of algorithmic logic [2,16] or a language of dynamic logic [11,29]). Operations on data types, leading from (more) primitive types to compound types, are defined in terms of the interpretability theory (cf. Szczerba [25]). The approach proposed here to defining new types accords with the methods of introducing new classes of objects in programming languages like Simula 67, Pascal, Loglan, Ada.
The Algebra of Control Machines and Its Applications to Control Automata and Glushkov’s Systems
Authors: Orlicki Andrzej
Published: May 2021

The main result of this paper is the description of the external behaviours of control automata, developing an algebra of these behaviours and making use of these behaviours to obtain the fundamental theorem of programming for the Glushkov system.
Generalized Polynomial-Time Reducibilities, Degrees and NP-Completeness
Authors: Schöning Uwe
Published: May 2021

An infinite hierarchy of polynomial-time reducibilities is introduced which generalizes the notion of polynomial-time Turing reducibility and strong nondeterministic polynomial-time Turing reducibility.
Remarks on the Complexity of Regulated Rewriting
Authors: Dassow Jürgen
Published: May 2021

We compare the description of languages by context free, Indian parallel, Russian parallel, programmed, matrix, and random context grammars with respect to the number of nonterminals.
Rough Sets and Information Systems
Authors: Marek Wiktor , Pawlak Zdzisław
Published: May 2021

We apply rough sets to characterize definable subsets of the universe of the information system.