Search results for "Data type"
showing 10 items of 1183 documents
Unavoidable sets and circular splicing languages
2017
Circular splicing systems are a formal model of a generative mechanism of circular words, inspired by a recombinant behaviour of circular DNA. They are defined by a finite alphabet A, an initial set I of circular words, and a set R of rules. In this paper, we focus on the still unknown relations between regular languages and circular splicing systems with a finite initial set and a finite set R of rules represented by a pair of letters ( ( 1 , 3 ) -CSSH systems). When R = A × A , it is known that the set of all words corresponding to the splicing language belongs to the class of pure unitary languages, introduced by Ehrenfeucht, Haussler, Rozenberg in 1983. They also provided a characteriza…
Verbal sets and cyclic coverings
2010
Abstract We consider groups G such that the set of all values of a fixed word w in G is covered by a finite set of cyclic subgroups. Fernandez-Alcober and Shumyatsky studied such groups in the case when w is the word [ x 1 , x 2 ] , and proved that in this case the corresponding verbal subgroup G ′ is either cyclic or finite. Answering a question asked by them, we show that this is far from being the general rule. However, we prove a weaker form of their result in the case when w is either a lower commutator word or a non-commutator word, showing that in the given hypothesis the verbal subgroup w ( G ) must be finite-by-cyclic. Even this weaker conclusion is not universally valid: it fails …
Miscellaneous Graph Preliminaries. Part I
2021
Summary This article contains many auxiliary theorems which were missing in the Mizar Mathematical Library to the best of the author’s knowledge. Most of them regard graph theory as formalized in the GLIB series and are needed in upcoming articles.
About Graph Complements
2020
Summary This article formalizes different variants of the complement graph in the Mizar system [3], based on the formalization of graphs in [6].
Span-Program-Based Quantum Algorithms for Graph Bipartiteness and Connectivity
2016
Span program is a linear-algebraic model of computation which can be used to design quantum algorithms. For any Boolean function there exists a span program that leads to a quantum algorithm with optimal quantum query complexity. In general, finding such span programs is not an easy task. In this work, given a query access to the adjacency matrix of a simple graph G with n vertices, we provide two new span-program-based quantum algorithms:an algorithm for testing if the graph is bipartite that uses $$On\sqrt{n}$$ quantum queries;an algorithm for testing if the graph is connected that uses $$On\sqrt{n}$$ quantum queries.
Using Search Algorithms for Modeling Economic Processes
2013
Abstract Economic issues are placed in formal practice, when is desired a modelling of the economic process, a manufacturing process, a device, etc. Each share of that economic process is denoted by a, b, c, d, these actions with defined time periods and action pairs are formed strings of the form, ab * cab * bc ., ab, bb, bc. so for them there are no other restrictions. If the graph is viewed as a system image, nodes representing components, then an immediate interpretation of an arc (xi, xj) are the component xi that is said to directly influence component xj. If nodes have the significance of possible states of a system when a spring (xi.xj) means that, the system can jump from state xi …
On the regularity of circular splicing languages : A survey and new developments
2009
Circular splicing has been introduced to model a specific recombinant behaviour of circular DNA, continuing the investigation initiated with linear splicing. In this paper we focus on the relationship between regular circular languages and languages generated by finite circular splicing systems. We survey the known results towards a characterization of the intersection between these two classes and provide new contributions on the open problem of finding this characterization. First, we exhibit a non-regular circular language generated by a circular simple system thus disproving a known result in this area. Then we give new results related to a restrictive class of circular splicing systems…
A Potential Field Function for Overlapping Point Set and Graph Cluster Visualization
2015
In this paper we address the problem of visualizing overlapping sets of points with a fixed positioning in a comprehensible way. A standard visualization technique is to enclose the point sets in isocontours generated by bounding a potential field function. The most commonly used functions are various approximations of the Gaussian distribution. Such an approach produces smooth and appealing shapes, however it may produce an incorrect point nesting in generated regions, e.g. some point is contained inside a foreign set region. We introduce a different potential field function that keeps the desired properties of Gaussian distribution, and in addition guarantees that every point belongs to a…
The branch set of a quasiregular mapping between metric manifolds
2016
Abstract In this note, we announce some new results on quantitative countable porosity of the branch set of a quasiregular mapping in very general metric spaces. As applications, we solve a recent conjecture of Fassler et al., an open problem of Heinonen–Rickman, and an open question of Heinonen–Semmes.
Termination of a set of rules modulo a set of equations
2006
The problem of termination of a set R of rules modulo a set E of equations, called E-termination problem, arises when trying to complete the set of rules in order to get a Church-Rosser property for the rules modulo the equations. We first show here that termination of the rewriting relation and E-termination are the same whenever the used rewriting relation is E-commuting, a property inspired from Peterson and Stickel’s E-compatibility property. More precisely, their results can be obtained by requiring termination of the rewriting relation instead of E-termination if E-commutation is used instead of E-compatibility. When the rewriting relation is not E-commuting, we show how to reduce E-t…