waashk/dblp huggingface dataset:
applications of standard sturmian words to elementary number theory. this note is a short survey, by no means intended to be complete, of some of the descriptions which have been given of standard sturmian words, and of some of the applications of these descriptions to elementary number theory. (`elementary number theory' is interpreted fairly broadly.) the descriptions and applications below have appeared before, except for fact 4, application 1, and the proof of application 2.
an improved deterministic local search algorithm for 3-sat. we slightly improve the pruning technique presented in dantsin et al. (theoret. comput. sci. 289 (2002) 69) to obtain an o*(1.473n) deterministic algorithm for 3-sat.
the complexity of fibonacci-like kneading sequences. the fibonacci(-like) unimodal maps that have been studied in recent years give rise to a zero-entropy minimal subshift on two symbols, generated by the kneading sequence. in this paper we computed the word-complexity of such subshifts exactly.
an algorithm reconstructing convex lattice sets. in this paper, we study the problem of reconstructing special lattice sets from x-rays in a finite set of prescribed directions. we present the class of "q-convex" sets which is a new class of subsets of z2 having a certain kind of weak connectedness. the main result of this paper is a polynomial-time algorithm solving the reconstruction problem for the "q-convex" sets. these sets are uniquely determined by certain finite sets of directions. as a result, this algorithm can be used for reconstructing convex subsets of z2 from their x-rays in some suitable sets of four lattice directions or in any set of seven mutually nonparallel lattice directions.
random generation of q-convex sets. the problem of randomly generating q-convex sets is considered. we present two generators. the first one uses the q-convex hull of a set of random points in order to generate a q-convex set included in the square [0, n)2. this generator is very simple, but is not uniform and its performance is quadratic in n. the second one exploits a coding of the salient points, which generalizes the coding of a border of polyominoes. it is uniform, and is based on the method by rejection. experimentally, this algorithm works in linear time in the length of the word coding the salient points. besides, concerning the enumeration problem, we determine an asymptotic formula for the number of q-convex sets according to the size of the word coding the salient points in a special case, and in general only an experimental estimation.
normal forms for algebras of connection. recent years have seen a growing interest towards algebraic structures that are able to express formalisms different from the standard, tree-like presentation of terms. many of these approaches reveal a specific interest towards the application to the 'distributed and concurrent systems' field, but an exhaustive comparison between them is sometimes difficult, because their presentations can be quite dissimilar. this work is a first step towards a unified view: focusing on the primitive ingredients of distributed spaces (namely interfaces, links and basic modules), we introduce a general schema for describing a normal form presentation of many algebraic formalisms, and show that those normal forms can be thought of as arrows of suitable monoidal categories.
a basic algebra of stateless connectors. the conceptual separation between computation and coordination in distributed computing systems motivates the use of peculiar entities commonly called connectors, whose task is managing the interaction among distributed components. different kinds of connectors exist in the literature at different levels of abstraction. we focus on an algebra of connectors that exploits five kinds of basic connectors (plus their duals), namely symmetry, synchronization, mutual exclusion, hiding and inaction. basic connectors can be composed in series and in parallel. we first define the operational, observational and denotational semantics of connectors, then we show that the observational and denotational semantics coincide and finally we give a complete normal-form axiomatization. the expressiveness of the framework is witnessed by the ability to model all the (stateless) connectors of the architectural design language community and of the coordination language reo.
dynamic connectors for concurrency. we propose a metatheoretic approach to the definition of operational and abstract concurrent semantics for systems where name handling is a key issue. the main ingredients of our framework are connectors and tile logic. the former allow for the modeling of various kinds of graph-like and term-like structures, which can be useful in representing system distribution and causal histories. the latter is used to combine the use of connectors in space and in time (i.e., according to configurations and computations). as a detailed case study, we show how to define a concurrent operational semantics and causal weak bisimilarity for a flavor of basic parallel processes.
semantic foundations for generalized rewrite theories. rewriting logic (rl) is a logic of actions whose models are concurrent systems. rewrite theories involve the specification of equational theories of data and state structures together with a set of rewrite rules that model the dynamics of concurrent systems. since its introduction, more than one decade ago, rl has attracted the interest of both theorists and practitioners, who have contributed in showing its generality as a semantic and logical framework and also as a programming paradigm. the experimentation conducted in these years has suggested that some significant extensions to the original definition of the logic would be very useful in practice. these extensions may develop along several dimensions, like the choice of the underlying equational logic, the kind of side conditions allowed in rewrite rules and operational concerns for the execution of certain rewrites. in particular, the maude system now supports subsorting and conditional sentences in the equational logic for data, and also frozen arguments to block undesired nested rewrites; moreover, it allows equality and membership assertions in rule conditions. in this paper, we give a detailed presentation of the inference rules, model theory, and completeness of such generalized rewrite theories. our results provide a mathematical semantics for maude, and a foundation for formal reasoning about maude specifications.
observational congruences for dynamically reconfigurable tile systems. the sos formats that ensure that bisimilarity is a congruence tail in the presence ot structural axioms on states. dynamic bisimulation, introduced to characterize the coarsest congruence for ccs which is also a weak bisimulation, reconciles the 'bisimilarity is a congruence' property with structural axioms and also with the specification of open ended systems, where states can be reconfigured at runtime. we show that the compositional framework offered by tile logic handles structural axioms and specifications of reconfigurable systems successfully. this allows for a finitary presentation of dynamic context closure, as internalized in the tile language. the case study of the π-calculus illustrates the main features of our approach. moreover, duality is exploited to model a second kind of reconfiguration: dynamic specialization.
on structuring proof search for first order linear logic. full first-order linear logic can be presented as an abstract logic programming language in miller's system forum, which yields a sensible operational interpretation in the 'proof search as computation' paradigm. however, forum still has to deal with syntactic details that would normally be ignored by a reasonable operational semantics. in this respect, forum improves on gentzen systems for linear logic by restricting the language and the form of inference rules. we further improve on forum by restricting the class of formulae allowed, in a system we call g-forum, which is still equivalent to full first-order linear logic. the only formulae allowed in g-forum have the same shape as forum sequents: the restriction does not diminish expressiveness and makes g-forum amenable to proof theoretic analysis. g-forum consists of two (big) inference rules, for which we show a cut elimination procedure. this does not need to appeal to finer detail in formulae and sequents than is provided by g-forum, thus successfully testing the internal symmetries of our system.
cumulative defect. we prove that if x is a finite code and s is an infinite word with 3 x-factorizations, then the rank r(x) of x is at most |x| - 2. more generally, if x belongs to a certain family of codes and s has l ≥ 2 x-factorizations, then the rank is at most |x| - l+ 1.
compatibility of unrooted phylogenetic trees is fpt. a collection of t1, t2,...,tk of unrooted, leaf labelled (phylogenetic) trees, all with different leaf sets, is said to be compatible if there exists a tree t such that each tree ti can be obtained from t by deleting leaves and contracting edges. determining compatibility is np-hard, and the fastest algorithm to date has worst case complexity of around ω(nk) time, n being the number of leaves. here, we present an o(nf(k)) algorithm, proving that compatibility of unrooted phylogenetic trees is fixed parameter tractable (fpt) with respect to the number k of trees.
representation of a class of nondeterministic semiautomata by canonical words. it has been shown recently that deterministic semiautomata can be represented by canonical words and equivalences; that work was motivated by the trace-assertion method for specifying software modules. here, we generalize these ideas to a class of nondeterministic semiautomata. a semiautomaton is settable if, for every state q, there exists a word wq such that q, and no other state, can be reached from some initial state by a path spelling wq. we extend many results from the deterministic case to settable nondeterministic semiautomata. now each word has a number of canonical representatives. we show that a prefix-rewriting system exists for transforming any word to any of its representatives. if the set of canonical words is prefix-continuous (meaning that, if w and a prefix u of w are in the set, then all prefixes of w longer than u are also in the set), the rewriting system has no infinite derivations. examples of specifications of nondeterministic modules are given.
maximizing agreements and coagnostic learning. this paper studies α-coagnostic learnability of classes of boolean formulas. to α-coagnostic learn c from h, the learner seeks a hypothesis h ∈ h whose probability of agreement (rather than disagreement as in agnostic learning) with a labeled example is within a factor α of the best agreement probability achieved by any f ∈ c. although 1-coagnostic learning is equivalent to agnostic learning, this is not true for α-coagnostic learning for 1/2 < α < 1.it can be seen that α-coagnostic learnability is equivalent to the α-approximability of the maximum agreement problems. for these problems we are given a labeled sample s and must find an h ∈ h that agrees with as many examples in s as the best f ∈ c does. many studies have been done on maximum agreement problems, for classes such as monomials, monotone monomials, antimonotone monomials, halfspaces and balls. we further the study of these problems and some extensions of them. for the above classes we improve the best previously known factors α for the hardness of α-coagnostic learning. we also find the first constant lower bounds for decision lists, exclusive-or, halfsaces (over the boolean domain), 2-term dnf and 2-term multivariate polynomials.
an equational notion of lifting monad. we introduce the notion of an equational lifting monad: a commutative strong monad satisfying one additional equation (valid for monads arising from partial map classifiers). we prove that any equational lifting monad has a representation by a partial map classifier such that the kleisli category of the former fully embeds in the partial category of the latter. thus, equational lifting monads precisely capture the equational properties of partial maps as induced by partial map classifiers. the representation theorem also provides a tool for transferring nonequational properties of partial map classifiers to equational lifting monads. it is proved using a direct axiomatization of kleisli categories of equational lifting monads. this axiomatization is of interest in its own right.
relative definability of boolean functions via hypergraphs. the aim of this work is to show how hypergraphs can be used as a systematic tool in the classification of continuous boolean functions according to their degree of parallelism. intuitively f is "less parallel" than g if it can be defined by a sequential program using g as its only free variable. it turns out that the poset induced by this preorder is (as for the degrees of recursion) a sup-semilattice. although hypergraphs have already been used in bucciarelli (theoret. comput. sci., to appear) as a tool for studying degrees of parallelism, no general result relating the former to the latter has been proved in that work. we show that the sup-semilattice of degrees has a categorical counterpart: we define a category of hypergraphs such that every object "represents" a monotone boolean function; finite coproducts in this category correspond to lubs of degrees. unlike degrees of recursion, where every set has a recursive upper bound, monotone boolean functions may have no sequential upper bound. however the ones which do have a sequential upper bound can be nicely characterised in terms of hypergraphs. these subsequential functions play a major role in the proof of our main result, namely that f is less parallel than g if there exists a morphism between their associated hypergraphs.
on finding common neighborhoods in massive graphs. we consider the problem of finding pairs of vertices that share large common neighborhoods in massive graphs. we prove lower bounds on the resources needed to solve this problem on resource-bounded models of computation. in streaming models, in which algorithms can access the input only a constant number of times and only sequentially, we show that, even with randomization, any algorithm that determines if there exists any pair of vertices with a large common neighborhood must essentially store and process the input graph off line. in sampling models, in which algorithms can only query an oracle for the common neighborhoods of specified vertex pairs, we show that any algorithm must sample almost every pair of vertices for their respective common neighborhoods.
a translation of tpal into a class of timed-probabilistic petri nets. tpalp is an algebraic language for the description of concurrent systems with capabilities to express timed and probabilistic behaviours, as well as urgent interactions. in this paper we present the main features of the language, its operational semantics, and a translation of tpalp terms into a particular class of timed-probabilistic petri nets. the language includes a probabilistic choice operator, a timed prefix operator, and an urgent prefix operator, as well as some other operators that we may find in classical process algebras. an important feature of the language is that urgency is considered at any instant by executing as many urgent actions as possible, with the goal of complying in a great extent with the urgent actions indicated in the user specifications.
complexity measures and decision tree complexity: a survey. we discuss several complexity measures for boolean functions: certificate complexity, sensitivity, block sensitivity, and the degree of a representing or approximating polynomial. we survey the relations and biggest gaps known between these measures, and show how they give bounds for the decision tree complexity of boolean functions on deterministic, randomized, and quantum computers.
h-coloring dichotomy revisited. the h-coloring problem can be expressed as a particular case of the constraint satisfaction problem (csp) whose computational complexity has been intensively studied under various approaches in the last several years. we show that the dichotomy theorem proved by hell and nešetřil [on the complexity of h-coloring, j. combin. theory ser. b 48 (1990) 92-110] for the complexity of the h-coloring problem for undirected graphs can be obtained using general methods for studying csp and that the criterion distinguishing the tractable cases of the h-coloring problem agrees with that conjectured in [a.a. bulatov, p.g. jeavons, a.a. krokhin, constraint satisfaction problems and finite algebras, in: proc. 27th internat. colloq. on automata, languages and programming--icalp'00, lecture notes in computer science, vol. 1853, springer, berlin, 2000, pp. 272-282] for the complexity of the general csp.
the complexity of partition functions. we give a complexity theoretic classification of the counting versions of so-called h-colouring problems for graphs h that may have multiple edges between the same pair of vertices. more generally, we study the problem of computing a weighted sum of homomorphisms to a weighted graph h.the problem has two interesting alternative formulations: first, it is equivalent to computing the partition function of a spin system as studied in statistical physics. and second, it is equivalent to counting the solutions to a constraint satisfaction problem whose constraint language consists of two equivalence relations.in a nutshell, our result says that the problem is in polynomial time if the adjacency matrix of h has row rank 1, and #p-hard otherwise.
lorentz gas cellular automata on graphs. lorentz gas cellular automata (lgca) are models of parallel many-tape turing machines generated by the motion of localized (point) objects (particles, signals, wave trains, etc.) on a graph. in each vertex v of the graph we store a symbol. a read/write head of the turing machine is represented as an object that hops from one vertex of the graph to another according to a rule (symbol) stored in the vertex. thus, the symbols stored in the vertices represent scattering rules (or simply scatterers) of the lattice gas. it is assumed that initially the scatterers are randomly distributed among the vertices of the graph. the random environment formed by the scatterers may either be fixed or evolve due to collisions with the moving object. the collisions simulate storing of a new symbol in the vertex of the graph. we investigate these models with fixed environment in general types of graphs and the models with evolving environments on trees. remarkably, it occurred that all models with fixed environments and many models with evolving environment behave like a depth-first search on the underlying graph. observe that such behavior occurs for any initial random distribution of scatterers rather than for some "specially prepared" initial configurations of scatterers. we also give estimates of periods of orbits on finite graphs.
projections of vector addition system reachability sets are semilinear. the reachability sets of vector addition systems of dimension six or more can be non-semilinear. this may be one reason why the inclusion problem (as well as the equality problem) for reachability sets of vector addition systems in general is undecidable, even though the reachability problem itself is known to be decidable. we show that any one-dimensional projection of the reachability set of an arbitrary vector addition system is semilinear, and hence, "simple".
approximating shortest path for the skew lines problem in time doubly logarithmic in 1/epsilon. we consider two three-dimensional situations when a polytime algorithm for approximating a shortest path can be constructed. the main part of the paper treats a well-known problem of constructing a shortest path touching lines in r3: given a list of straight lines l = (l1,..., ln) in r3 and two points s and t, find a shortest path that, starting from s, touches the lines li in the given order and ends at t. we remark that such a shortest path is unique. we show that it can be length--position ε-approximated (i.e. both its length and its position can be found approximately) in time (rn/dα)16 + o(n2 log log 1/ε), where d is the minimal distance between consecutive lines of l, α˜ is the minimum of sines of angles between consecutive lines, and r is the radius of a ball where the initial approximation can be placed (such a radius can be easily computed from the initial data).as computational model we take real ram extended by square and cubic roots extraction. this problem of constructing a shortest path touching lines is known for quite some time to be a challenging problem. the existing methods for approximating shortest paths based on adding steiner points which form a grid and subsequently applying dijkstra's algorithm for finding a shortest path in the grid, provide a complexity bound which depends polynomially on 1/ε, while our algorithm for the problem under consideration has complexity linear in log log 1/ε. our algorithm is motivated by the observation that the shortest path in question is a geodesic in a certain length space of non-positive curvature (in the sense of a.d. alexandrov), and it relies on the (elementary) theory of cat(0)-spaces.in the second part of the paper we analyze very simple grid approximations. we assume that a parameter a > 0 describing separability of obstacles is given and the part of a grid with mesh size a outside the obstacles is built (for semi-algebraic obstacles all these precalculations are polytime). we show that there is an algorithm of time complexity o((1/a)6) which, given a-separated obstacles in a unit cube, finds a path (between given vertices s and t of the grid) whose length is bounded from above by (84π* + 96a), where π* is the length of a shortest path. on the other hand, as we show by an example, one cannot approximate the length of a shortest path better than 7π* if one uses only grid polygons (constructed only from grid edges). for semi-algebraic obstacles our computational model is bitwise. for a general type of obstacles the model is bitwise modulo constructing the part of the grid admissible for our paths. observe that the existing methods for approximating shortest paths are not directly applicable for semi-algebraic obstacles since they usually place the steiner points forming a grid on the edges of polyhedral obstacles.
sequential computation of linear boolean mappings. we prove that any linear boolean mapping of dimension n can be computed with a double sequence of linear assignments of the n variables. the proof is effective and gives a decomposition of boolean matrices and directed graphs.
a note on iterated duals of certain topological spaces. problem 540 in open problems in topology (1990) asks whether iterating the operation of taking the dual topology eventually leads to a mutually dual pair of topologies. we give an affirmative answer to problem 540 for several classes of spaces. some of the special cases covered are: any t1 space (already solved in 1966 by strecker), the lower vietoris topology on any hyperspace, the scott topology for reverse inclusion on any hyperspace, and the upper vietoris topology on the hyperspace of a regular space. we find in all these cases that tdd=tdddd, and therefore at most four distinct topologies, t,td,tdd,tddd, can be created by iterating the dual operator starting with any one of these special cases.