bluuebunny/crossref_metadata_2025_split huggingface dataset:
Succinctness of two-way probabilistic and quantum finite automata
Authors: Yakaryilmaz Abuzer , Say A. C. Cem 
Published: August 2021

special issue dedicated to the second edition of the conference AutoMathA: from Mathematics to Applications
We introduce a new model of two-way finite automaton, which is endowed with the capability of resetting the position of the tape head to the left end of the tape in a single move during the computation. Several variants of this model are examined, with the following results: The weakest known model of computation where quantum computers recognize more languages with bounded error than their classical counterparts is identified. We prove that two-way probabilistic and quantum finite automata (2PFAs and 2QFAs) can be considerably more concise than both their one-way versions (1PFAs and 1QFAs), and two-way nondeterministic finite automata (2NFAs). For this purpose, we demonstrate several infinite families of regular languages which can be recognized with some fixed probability greater than 1 2 by just tuning the transition amplitudes of a 2QFA (and, in one case, a 2PFA) with a constant number of states, whereas the sizes of the corresponding 1PFAs, 1QFAs and 2NFAs grow without bound. We also show that 2QFAs with mixed states can support highly efficient probability amplification.
Noneffective Regularity of Equality Languages and Bounded Delay Morphisms
Authors: Karhumaki Juhani , Saarela Aleksi 
Published: August 2021

special issue dedicated to the second edition of the conference AutoMathA: from Mathematics to Applications
We give an instance of a class of morphisms for which it is easy to prove that their equality set is regular, but its emptiness is still undecidable. The class is that of bounded delay 2 morphisms.
Grammatical compression: compressed equivalence and other problems
Authors: Bertoni Alberto , Radicioni Roberto 
Published: August 2021

special issue dedicated to the second edition of the conference AutoMathA: from Mathematics to Applications
In this work, we focus our attention to algorithmic solutions for problems where the instances are presented as straight-line programs on a given algebra. In our exposition, we try to survey general results by presenting some meaningful examples; moreover, where possible, we outline the proofs in order to give an insight of the methods and the techniques. We recall some recent results for the problem PosSLP, consisting of deciding if the integer defined by a straight-line program on the ring Z is greater than zero; we discuss some implications in the areas of numerical analysis and strategic games. Furthermore, we propose some methods for reducing Compressed Word Problem from an algebra to another; reductions from trace monoids to the semiring of nonnegative integers are exhibited and polynomial time algorithms for compressed equivalence in monoids related to Dyck reductions are shown. Finally, we consider inclusion problems for context-free languages, proving how in some cases efficient algorithms for these problems benefit from the ability to work with compressed data.
A de Bruijn - Erdos theorem and metric spaces
Authors: Chiniforooshan Ehsan , Chvatal Vasek 
Published: August 2021

Combinatorics
De Bruijn and Erdos proved that every noncollinear set of n points in the plane determines at least n distinct lines. Chen and Chvatal suggested a possible generalization of this theorem in the framework of metric spaces. We provide partial results in this direction.
Computing tensor decompositions of finite matrix groups
Authors: Ankaralioglu Nurullah , Seress Akos 
Published: August 2021

special issue in honor of Laci Babai's 60th birthday: Combinatorics, Groups, Algorithms, and Complexity
We describe an algorithm to compute tensor decompositions of central products of groups. The novelty over previous algorithms is that in the case of matrix groups that are both tensor decomposable and imprimitive, the new algorithm more often outputs the more desirable tensor decomposition.
The Join of the Varieties of R-trivial and L-trivial Monoids via Combinatorics on Words
Authors: Kufleitner Manfred , Lauser Alexander 
Published: August 2021

Automata, Logic and Semantics
The join of two varieties is the smallest variety containing both. In finite semigroup theory, the varieties of R-trivial and L-trivial monoids are two of the most prominent classes of finite monoids. Their join is known to be decidable due to a result of Almeida and Azevedo. In this paper, we give a new proof for Almeida and Azevedo's effective characterization of the join of R-trivial and L-trivial monoids. This characterization is a single identity of omega-terms using three variables.
Monadic Second-Order Classes of Forests with a Monadic Second-Order 0-1 Law
Authors: Bell Jason P. , Burris Stanley N. , Yeats Karen A. 
Published: August 2021

Automata, Logic and Semantics
Let T be a monadic-second order class of finite trees, and let T(x) be its (ordinary) generating function, with radius of convergence rho. If rho >= 1 then T has an explicit specification (without using recursion) in terms of the operations of union, sum, stack, and the multiset operators n and (>= n). Using this, one has an explicit expression for T(x) in terms of the initial functions x and x . (1 - x(n))(-1), the operations of addition and multiplication, and the Polya exponentiation operators E-n, E-(>= n). Let F be a monadic-second order class of finite forests, and let F (x) = Sigma(n) integral(n)x(n) be its (ordinary) generating function. Suppose F is closed under extraction of component trees and sums of forests. Using the above-mentioned structure theory for the class T of trees in F, Compton's theory of 0-1 laws, and a significantly strengthened version of 2003 results of Bell and Burris on generating functions, we show that F has a monadic second-order 0-1 law iff the radius of convergence of F (x) is 1 iff the radius of convergence of T (x) is >= 1.
A linear time algorithm for finding an Euler walk in a strongly connected 3-uniform hypergraph
Authors: Lonc Zbigniew , Naroski Pawel 
Published: August 2021

Discrete Algorithms
By an Euler walk in a 3-uniform hypergraph H we mean an alternating sequence v(0), epsilon(1), v(1), epsilon(2), v(2), ... , v(m-1), epsilon(m), v(m) of vertices and edges in H such that each edge of H appears in this sequence exactly once and v(i-1); v(i) is an element of epsilon(i), v(i-1) not equal v(i), for every i = 1, 2, ... , m. This concept is a natural extension of the graph theoretic notion of an Euler walk to the case of 3-uniform hypergraphs. We say that a 3-uniform hypergraph H is strongly connected if it has no isolated vertices and for each two edges e and f in H there is a sequence of edges starting with e and ending with f such that each two consecutive edges in this sequence have two vertices in common. In this paper we give an algorithm that constructs an Euler walk in a strongly connected 3-uniform hypergraph (it is known that such a walk in such a hypergraph always exists). The algorithm runs in time O(m), where m is the number of edges in the input hypergraph.
Vertex-colouring edge-weightings with two edge weights
Authors: Khatirinejad Mahdad , Naserasr Reza , Newman Mike , Seamone Ben , Stevens Brett 
Published: August 2021

Graphs and Algorithms
An edge-weighting vertex colouring of a graph is an edge-weight assignment such that the accumulated weights at the vertices yields a proper vertex colouring. If such an assignment from a set S exists, we say the graph is S-weight colourable. It is conjectured that every graph with no isolated edge is \1, 2, 3\-weight colourable. We explore the problem of classifying those graphs which are \1, 2\ -weight colourable. We establish that a number of classes of graphs are S -weight colourable for much more general sets S of size 2. In particular, we show that any graph having only cycles of length 0 mod 4 is S -weight colourable for most sets S of size 2. As a consequence, we classify the minimal graphs which are not \1, 2\-weight colourable with respect to subgraph containment. We also demonstrate techniques for constructing graphs which are not \1, 2\-weight colourable.
On bipartite powers of bigraphs
Authors: Okamoto Yoshio , Otachi Yota , Uehara Ryuhei 
Published: August 2021

Graph Theory
The notion of graph powers is a well-studied topic in graph theory and its applications. In this paper, we investigate a bipartite analogue of graph powers, which we call bipartite powers of bigraphs. We show that the classes of bipartite permutation graphs and interval bigraphs are closed under taking bipartite power. We also show that the problem of recognizing bipartite powers is NP-complete in general.
The analysis of find and versions of it
Authors: Knof Diether , Roesler Uwe 
Published: August 2021

Analysis of Algorithms
In the running time analysis of the algorithm Find and versions of it appear as limiting distributions solutions of stochastic fixed points equation of the form X D = Sigma(i) AiXi o Bi + C on the space D of cadlag functions. The distribution of the D-valued process X is invariant by some random linear affine transformation of space and random time change. We show the existence of solutions in some generality via the Weighted Branching Process. Finite exponential moments are connected to stochastic fixed point of supremum type X D = sup(i) (A(i)X(i) + C-i) on the positive reals. Specifically we present a running time analysis of m-median and adapted versions of Find. The finite dimensional distributions converge in L-1 and are continuous in the cylinder coordinates. We present the optimal adapted version in the sense of low asymptotic average number of comparisons. The limit distribution of the optimal adapted version of Find is a point measure on the function [0, 1] there exists t -> 1 + mint, 1 - t.
Graphs with many vertex-disjoint cycles
Authors: Rautenbach Dieter , Regen Friedrich 
Published: August 2021

Graph Theory
We study graphs G in which the maximum number of vertex-disjoint cycles nu(G) is close to the cyclomatic number mu(G), which is a natural upper bound for nu(G). Our main result is the existence of a finite set P(k) of graphs for all k is an element of N-0 such that every 2-connected graph G with mu(G)-nu(G) = k arises by applying a simple extension rule to a graph in P(k). As an algorithmic consequence we describe algorithms calculating minmu(G)-nu(G), k + 1 in linear time for fixed k.
Clique cycle transversals in graphs with few P₄'s
Authors: Bravo Raquel , Klein Sulamita , Nogueira Loana Tito , Protti Fábio 
Published: August 2021

Graph Theory
A graph is extended P4-laden if each of its induced subgraphs with at most six vertices that contains more than two induced P4's is 2K2,C4-free. A cycle transversal (or feedback vertex set) of a graph G is a subset T ⊆ V (G) such that T ∩ V (C) 6= ∅ for every cycle C of G; if, in addition, T is a clique, then T is a clique cycle transversal (cct). Finding a cct in a graph G is equivalent to partitioning V (G) into subsets C and F such that C induces a complete subgraph and F an acyclic subgraph. This work considers the problem of characterizing extended P4-laden graphs admitting a cct. We characterize such graphs by means of a finite family of forbidden induced subgraphs, and present a linear-time algorithm to recognize them.
A new characterization and a recognition algorithm of Lucas cubes
Authors: Taranenko Andrej 
Published: August 2021

Graph Theory
Fibonacci and Lucas cubes are induced subgraphs of hypercubes obtained by excluding certain binary strings from the vertex set. They appear as models for interconnection networks, as well as in chemistry. We derive a characterization of Lucas cubes that is based on a peripheral expansion of a unique convex subgraph of an appropriate Fibonacci cube. This serves as the foundation for a recognition algorithm of Lucas cubes that runs in linear time.
A chip-firing variation and a new proof of Cayley's formula
Authors: Kayll Peter Mark , Perkins Dave 
Published: August 2021

Graph Theory
We introduce a variation of chip-firing games on connected graphs. These 'burn-off' games incorporate the loss of energy that may occur in the physical processes that classical chip-firing games have been used to model. For a graph G=(V,E), a configuration of 'chips' on its nodes is a mapping C:V→ℕ. We study the configurations that can arise in the course of iterating a burn-off game. After characterizing the 'relaxed legal' configurations for general graphs, we enumerate the 'legal' ones for complete graphs Kn. The number of relaxed legal configurations on Kn coincides with the number tn+1 of spanning trees of Kn+1. Since our algorithmic, bijective proof of this fact does not invoke Cayley's Formula for tn, our main results yield secondarily a new proof of this formula.
All totally symmetric colored graphs
Authors: Grech Mariusz , Kisielewicz Andrzej 
Published: August 2021

Graph Theory
In this paper we describe all edge-colored graphs that are fully symmetric with respect to colors and transitive on every set of edges of the same color. They correspond to fully symmetric homogeneous factorizations of complete graphs. Our description completes the work done in our previous paper, where we have shown, in particular, that there are no such graphs with more than 5 colors. Using some recent results, with a help of computer, we settle all the cases that was left open in the previous paper.
Evaluating the impact of faculty development programme initiative: are we really improving skills in MCQ writing?
Authors: Kiran Faiza , Ayub Rukhsana , Rauf Ayesha , Qamar Khadija 
Published: August 2021

Objective: This study was done to evaluate the effectiveness of a 3-hour workshop in improving faculty competence in developing high quality test items.
Methodology: The study took place in National University of Medical Sciences and its affiliated institutes in Pakistan, during a period of six months in year 2018. It was a descriptive, cross sectional study. A series of seven workshops on quality assurance in writing MCQs was conducted as part of faculty development program, emphasizing hand-on experience and prompt feedback. Participants’ satisfaction was evaluated with a post-workshop feedback questionnaire (Kirkpatrick 1). A self-made structured questionnaire was given as a pre-test and post-test, to check improvement in cognition, behaviour and item writing skills of faculty (Kirkpatrick 2). Paired t test was applied and difference in mean scores of responses was evaluated.
Results: Total 141 faculty members were trained. The training session led to high satisfaction in all elements of workshop, significant improvements in boosting confidence in item writing skills(p=0.000), recognizing parts of MCQs (p=0.000), identifying item writing flaws (p=0.000) and levels of Millers pyramid and blooms taxonomy (p=0.000).
Conclusion: Training sessions of short duration are effective in improving the competence of faculty in writing quality test items, provided hands-on experience is built-in and effective feedback is provided.
FACTORS INFLUENCING CLINICAL MANAGEMENT OF CRYPTOCOCCAL MENINGITIS AMONG HEALTH CARE PROVIDERS AT TWO REFERRAL HOSPITALS IN KISUMU COUNTY, KENYA
Authors: Ogendo Robina 
Published: August 2021

Purpose: Cryptococcal meningitis is one of the most common and lethal opportunistic infections among human immune virus infected clients/patients before initiation of antiretroviral therapy. It is majorly associated to morbidity and early mortality among human immunodeficiency virus infected patients in resource limited countries. The main objective of this study was to investigate the factors influencing clinical management of cryptococcal meningitis in adults among health care providers at two referral hospitals in Kisumu County, Kenya.
Methodology: A cross-sectional study using quantitative approach was used targeting 119 health care providers. Collection of data was through pretested self- administered questionnaires to examine factors influencing clinical management of cryptococcal meningitis. Data obtained was analyzed using the statistical package for social science version 25. Descriptive analysis was done using frequencies, percentages and means. Inferential analysis was conducted using bivariate logistic regression to determine relationships among the variables, p-values of at or below 0.05 were considered statistically significant.
Results: The major factor associated positively with clinical management of cryptococcal meningitis was the acknowledgement by the health care providers that the world health organization guidelines lead to a better patient outcome (97%, n=113) and inadequate supplies and resources to facilitate management (78%, n=90) was the major factor associated negatively. Health care providers with an experience of five years or less were 40% more likely to agree that the factors were influencing clinical management of cryptococcal meningitis in contrast to those with an experience of six years or more (OR: 0.6; 95%CI: 0.1 – 0.74; p=0.04).
Unique contribution to theory, practice and policy: The clinical management of cryptococcal meningitis in adults in the study area is majorly negatively influenced by inadequate supplies and resources to facilitate the process of management. The study recommends that the policy makers in the County government of Kisumu and the two hospital management teams need to scale up a timely and constant provision of adequate resources, facilities and supplies, which will promote effective clinical management of cryptococcal meningitis in the study area
ANALISIS PENGARUH UKURAN PERUSAHAAN, KUALITAS AUDITOR, PROFITABILITAS, DAN LIKUIDITAS TERHADAP OPINI GOING CONCERN PADA PERUSAHAAN JASA YANG TERCATAT DI BURSA EFEK INDONESIA PERIODE 2016-2018
Authors: Simanjuntak Daniel Nicson 
Published: August 2021

ABSTRACT
The purpose of this study is to analyse the effects of company size, auditor’s quality, profitability and liquidity on going concern opinion of the service companies listed on Indonesia Stock Exchange in the period of 2016 to 2018.
This study is a quantitative research with causal comparative method and used secondary data. The population in this study covers all sectors of the service companies listed on Indonesia Stock Exchange which amounted 417 companies. There are 33 (thirty three) companies used as samples in this study, with the purposive sampling as the sampling technique and logistic regression for the data analysis.
The results of this study indicates that auditor’s quality and liquidity have negative effect and significant on acceptance of going concern opinion with the significance level are 0,014 and 0,010. Meanwhile, company size has positive effect but not significant and profitability has negative effect but not significant to the acceptance of going concern opinion with the significance level are 0,555 and 0,431. And simultaneously independent variables such as company size, auditor’s quality, profitability, and liquidity are all having significant affect on dependent variable which is going concern opinion with the significance level of 88% with the rest of 12% affected by other variables apart from the research.
Ecohydrological travel times derived from in situ stable water isotope measurements in trees during a semi-controlled pot experiment
Authors: Mennekes David , Rinderer Michael , Seeger Stefan , Orlowski Natalie 
Published: August 2021

Abstract. Tree water uptake processes and ecohydrological travel times have gained more attention in recent ecohydrological studies. In situ measurement techniques for stable water isotopes offer great potential to investigate these processes but have not been applied much to tree xylem and soils so far. Here, we used in situ probes for stable water isotope measurements to monitor the isotopic signatures of soil and tree xylem water before and after two deuterium-labeled irrigation experiments. To show the potential of the method, we tested our measurement approach with 20-year-old trees of three different species (Pinus pinea, Alnus incana and Quercus suber). They were planted in large pots with homogeneous soil in order to have semi-controlled experimental conditions. Additional destructive sampling of soil and plant material allowed for a comparison between destructive (cryogenic vacuum extraction and direct water vapor equilibration) and in situ isotope measurements. Furthermore, isotope-tracer-based ecohydrological travel times were compared to travel times derived from sap flow measurements. The time to first arrival of the isotope tracer signals at 15 cm stem hight were ca. 17 h for all tree species and matched well with sap-flow-based travel times. However, at 150 cm stem height tracer-based travel times differed between tree species and ranged between 2.4 and 3.3 d. Sap-flow-based travel times at 150 cm stem hight were ca. 1.3 d longer than tracer-based travel times. The isotope signature of destructive and in situ isotope measurements differed notably, which suggests that the two types of techniques sampled water from different pools. In situ measurements of soil and xylem water were much more consistent between the three tree pots (on average standard deviations were smaller by 8.4 ‰ for δ2H and by 1.6 ‰ for δ18O for the in situ measurements) and also among the measurements from the same tree pot in comparison to the destructive methods (on average standard deviations were smaller by 7.8 ‰ and 1.6 ‰ for δ2H and δ18O, respectively). Our study demonstrates the potential of semi-controlled large-scale pot experiments and very frequent in situ isotope measurements for monitoring tree water uptake and ecohydrological travel times. It also shows that differences in sampling techniques or sensor types need to be considered when comparing results of different studies and within one study using different methods.
MICROEMPREENDEDOR INDIVIDUAL (MEI): UMA ANÁLISE DO PERFIL NO MUNICÍPIO DE PARANAGUÁ/PR (2010-2017)
Authors: Spagnollo Maria Cristina Izidro , Junckes Ivan Jairo 
Published: August 2021

O artigo explora o quantitativo de optantes pelo microempreendedor individual para conhecer e discutir minimamente os sujeitos na sua formalização. Para o desenvolvimento desta investigação, foi realizado um levantamento do perfil do MEI nos últimos oito anos (2010 - 2017), no município de Paranaguá, considerando as seguintes características: sexo, faixa etária e CNAE. Após um levantamento teórico, foi possível notar uma escassez nos trabalhos realizados Microempreendedor no Litoral do Paraná e a inexistência de um artigo desenvolvido especialmente para este município. Neste contexto para o desenvolvimento deste trabalho, foi realizada uma pesquisa bibliográfica e uma análise quantitativa com base nos dados extraídos do Portal do Empreendedor. Os resultados demonstram que o perfil do microempreendedor é composto em sua maioria por mulheres, na faixa etária entre 31 e 40 anos se concentrando principalmente em atividades de comércio/confecção de vestuário e/ou acessórios. O perfil do MEI em Paranaguá aponta para a necessidade de um reforço nas políticas públicas dirigidas à capacitação das mulheres no mercado de serviços. Palavras-chave: MEI. Microempreendedor Individual. Políticas Públicas. Empreendedorismo. Paranaguá.