waashk/dblp huggingface dataset:
codes defined by multiple sets of trajectories. we investigate the use of shuffle on trajectories to model certain classes of languages arising in the theory of codes. in particular, for each finite set of sets of trajectories, which we call a hyperset of trajectories, we define a class of languages induced by that hyperset of trajectories. we investigate the properties of hypersets of trajectories and the associated classes of languages, including the problem of decidability of membership and the problem of equivalence of hypersets of trajectories.
finite semigroups, feedback, and the letichevsky criteria on non-empty words in finite automata. this paper relates classes of finite automata under various feedback products to some well-known pseudovarieties of finite semigroups via a study of their irreducible divisors (in the sense of krohn-rhodes). in particular, this serves to relate some classical results of krohn, rhodes, stiffler, eilenberg, letichevsky, gécseg, ésik, and horváth. we show that for a finite automaton satisfaction of (1) the letichevsky criterion for non-empty words, (2) the semi-letichevsky criterion for non-empty words, or (3) neither criterion, corresponds, respectively, to the following properties of the characteristic semigroup of the automaton: (1) non-constructability as a divisor of a cascade product of copies of the two-element monoid with zero u, (2) such constructability while having u but no other non-trivial irreducible semigroup as a divisor, or (3) having no non-trivial irreducible semigroup divisors at all. the latter two cases are exactly the cases in which the characteristic semigroup is r-trivial.this algebraic characterization supports the transfer of results about finite automata to results about finite semigroups (and vice versa), and yields insight into the lattice of pseudovarieties of finite semigroups--or, equivalently via the eilenberg correspondence, the lattice of +-varieties of regular languages--and the operators on these lattices that are naturally associated to various automata products with bounded feedback. in particular, all operators with non-trivial feedback are shown to be equivalent, and we characterize all pseudovarieties of finite semigroups closed under each type of feedback product either explicitly or by reducing the question to closure under the cascade product.
from local to global temporal logics over mazurkiewicz traces. we review some results on global and local temporal logic on mazurkiewicz traces. our main contribution is to show how to derive the expressive completeness of global temporal logic with respect to first-order logic [v. diekert, p. gastin, ltl is expressively complete for mazurkiewicz traces, j. comput. system sci. 64 (2002) 396-418] from the similar result on local temporal logic [v. diekert, p. gastin, pure future local temporal logics are expressively complete for mazurkiewicz traces, in: m. farach-colton (ed.), proc. latin'04, lecture notes in computer science, vol. 2976, springer, berlin, 2004, pp. 232-241, full version available as research report lsv-05-22, laboratoire spécification et vérification, ens cachan, france].
selecting evaluation functions in opponent-model search. opponent-model search is a game-tree search method that explicitly uses knowledge of the opponent. there is some risk involved in using opponent-model search. for adequate forecasting, two conditions should be imposed. both the prediction of the opponent's moves and the judgement of future positions should be of good quality. the two conditions heavily depend on the evaluation functions used.in the article we distinguish evaluation functions by type. three fundamentally different types are introduced. thorough analysis of a variety of characteristics leads to eight possible orderings. the role of the evaluation functions is studied by attempting to answer five research questions. moreover, actual computer game-playing programs investigate the research questions by a series of experiments in which opponent-model search is performed. the game of bao is our test bed, it was selected because of its relatively narrow game tree, which allowed for an appropriate search depth in the experiments. we restrict ourselves to five evaluation functions generated with the help of machine-learning techniques. a set of round-robin tournaments between these evaluation functions show that when the above conditions are met, opponent-model search can be applied successfully. answers to the research questions are given in the conclusions.
er modelling from first relational principles. entity-relationship (er) modelling as a popular technique for data modelling. despite its popularity and widespread use, it lacks a firm semantic foundation. we propose a translation of an er-model into relation algebra, suggesting that this kind of algebra does provide suitable mechanisms for establishing a formal semantics of er modelling. the work reported on here deals first with the techniques necessary for the translation, thus constructing a static view of an er-model in an abstract setting of what might be called logic without variables. we then undertake a detailed analysis of the insertion and deletion operations for an er-model represented in terms of the relation calculus.
optimal semi-online preemptive algorithms for machine covering on two uniform machines. in this paper, we consider the semi-online preemptive scheduling problem with decreasing job sizes on two uniform machines. our goal is to maximize the continuous period of time (starting from time zero) when both machines are busy, which is equivalent to maximizing the minimum machine completion time if idle time is not introduced before all the jobs are completed. we design optimal deterministic semi-online algorithms for every machine speed ratio s ∈ [1, ∞), and show that idle time is required during the assignment procedure of algorithms for any s > √6/2. the competitive ratios of the algorithms match the randomized lower bound for every 1 ≤ s ≤ 3. the problem of whether randomization still does not help for the discussed preemptive scheduling problem remains open.
ant colony optimization theory: a survey. research on a new metaheuristic for optimization is often initially focused on proof-of-concept applications. it is only after experimental work has shown the practical interest of the method that researchers try to deepen their understanding of the method's functioning not only through more and more sophisticated experiments but also by means of an effort to build a theory. tackling questions such as "how and why the method works" is important, because finding an answer may help in improving its applicability. ant colony optimization, which was introduced in the early 1990s as a novel technique for solving hard combinatorial optimization problems, finds itself currently at this point of its life cycle. with this article we provide a survey on theoretical results on ant colony optimization. first, we review some convergence results. then we discuss relations between ant colony optimization algorithms and other approximate methods for optimization. finally, we focus on some research efforts directed at gaining a deeper understanding of the behavior of ant colony optimization algorithms. throughout the paper we identify some open questions with a certain interest of being solved in the near future.
the impact of information on broadcasting time in linear radio networks. we consider the problem of distributed deterministic broadcasting in radio networks whose nodes are located on a line. nodes send messages in synchronous time-slots. each node υ has a given transmission range. all nodes located within this range can receive messages from υ. however, a node situated in the range of two or more nodes that send messages simultaneously, cannot receive these messages and hears only noise. each node knows only its own position and range, as well as the maximum of all ranges. broadcasting is adaptive: nodes can decide on the action to take on the basis of previously received messages, silence or noise. we prove lower bounds on broadcasting time in this model and construct broadcasting protocols whose performance nearly matches these bounds for the simplest case when nodes are situated on a line. we also show that if nodes do not even know their own range, every broadcasting protocol must be hopelessly slow. while distributed randomized broadcasting algorithms, and, on the other hand, deterministic off-line broadcasting algorithms assuming full knowledge of the radio network, have been extensively studied in the literature, ours are the first results concerning broadcasting algorithms that are distributed and deterministic at the same time. we show that in this case, information available to nodes influences the efficiency of broadcasting in a significant way.
normal forms for binary relations. we consider the representable equational theory of binary relations, in a language expressing composition, converse, and lattice operations. by working directly with a presentation of relation expressions as graphs we are able to define a notion of reduction which is confluent and strongly normalizing and induces a notion of computable normal form for terms. this notion of reduction thus leads to a computational interpretation of the representable theory.
an efficient algorithm for computing bisimulation equivalence. we propose an efficient algorithmic solution to the problem of determining a bisimulation relation on a finite structure working both on the explicit and on the implicit (symbolic) representation. as far as the explicit case is concerned, starting from a set-theoretic point of view we propose an algorithm that optimizes the solution to the relational coarsest partition problem given by paige and tarjan (siam j. comput. 16(6) (1987) 973); its use in model-checking packages is also discussed and tested. for well-structured graphs our algorithm reaches a linear worst-case behaviour. the proposed algorithm is then re-elaborated to produce a symbolic version.
neural computation, social networks, and topological spectra. this paper emphasizes some intriguing links between neural computation on graphical domains and social networks, like those used in nowadays search engines to score the page authority. it is pointed out that the introduction of web domains creates a unified mathematical framework for these computational schemes. it is shown that one of the major limitations of currently used connectionist models, namely their scarce ability to capture the topological features of patterns, can be effectively faced by computing the node rank according to social-based computation, like google's pagerank. the main contribution of the paper is the introduction of a novel graph spectral notion, which can be naturally used for the graph isomorphism problem. in particular, a class of graphs is introduced for which the problem is proven to be polynomial. it is also pointed out that the derived spectral representations can be nicely combined with learning, thus opening the doors to many applications typically faced within the framework of neural computation.
uniformly hard languages. ladner (j. assoc. comput. mach. 22 (1975) 155) showed that there are no minimal recursive sets under polynomial-time reductions. given any recursive set a, ladner constructs a set b such that b strictly reduces to a but b does not lie in p. the set b does have very long sequences of input lengths of easily computable instances.we examine whether ladner's results hold if we restrict ourselves to "uniformly hard languages" which have no long sequences of easily computable instances. under a hard to disprove assumption, we show that there exists a minimal recursive uniformly hard set under honest many-one polynomial-time reductions.
a representation theorem for boolean contact algebras. we prove a representation theorem for boolean contact algebras which implies that the axioms for the region connection calculus (rcc) [d.a. randell, a.g. cohn, z. cui, computing transitivity tables: a challenge for automated theorem provers, in: d. kapur (ed.), proceedings of the 11th international conference on automated deduction (cade-11), lecture notes in artificial intelligence, vol. 607, springer, saratoga, springs, ny, 1992, pp. 786-790] are complete for the class of subalgebras of the algebras of regular closed sets of weakly regular connected t1 spaces.
on kurtz randomness. kurtz randomness is a notion of algorithmic randomness for real numbers. in particular a real x is called kurtz random (or weakly random) iff it is contained in every computably enumerable set u of (lebesgue) measure 1. we prove a number of characterizations of this notion, relating it to other notions of randomness such as the well-known notions of computable randomness, martin-löf randomness and schnorr randomness. for the first time we give machine characterizations of kurtz randomness. whereas the turing degree of every martin-löf random c.e. real is the complete degree, and the degrees of schnorr random c.e. reals are all high, we show that kurtz random c.e. reals occur in every non-zero c.e. degree. additionally, we show that the sets that are low for kurtz randomness are all hyperimmune and include those that are low for schnorr randomness, characterized previously by terwijn and zambella.@ 2004 elsevier b.v. all rights reserved.
structured theories and institutions. category theory provides an excellent foundation for studying structured specifications and their composition. for example, theories can be structured together in a diagram, and their composition can be obtained as a colimit. there is, however, a growing awareness, both in theory and in practice, that structured theories should not be viewed just as the "scaffolding" used to build unstructured theories: they should become first-class citizens in the specification process. given a logic formalized as an institution i, we therefore ask whether there is a good definition of the category of structured i-theories, and whether they can be naturally regarded as the ordinary theories of an appropriate institution j(i) generalizing the original institution i. we answer both questions in the affirmative, and study good properties of the institution i inherited by j(i). we show that, under natural conditions, a number of important properties are indeed inherited, including cocompleteness of the category of theories, liberality, and extension of the basic framework by freeness constraints. the results presented here have been used as a foundation for the module algebra of the maude language, and seem promising as a semantic basis for a generic module algebra that could be both specified and executed within the logical framework of rewriting logic.
presentations of computably enumerable reals. we study the relationship between a computably enumerable real and its presentations: ways of approximating the real by enumerating a prefix-free set of binary strings.
de la logique aux pavages. l'objectif de cet article de synth&eacute;se est de pr&eacute;senter ensemble un certain nombre de r&eacute;sultats liant les pavages &aacute; la logique suivant divers points de vue: certains structurels, d'autres plus algorithmiques en termes d'ind&eacute;cidabilit&eacute;, de complexit&eacute;s.
number-conserving cellular automata i: decidability. we prove that definitions of number-conserving cellular automata found in literature are equivalent. a necessary and sufficient condition for cellular automata to be number-conserving is proved. using this condition, we give a quasi-linear time algorithm to decide number-conservation.
criteria to disprove context freeness of collage languages. collage grammars are context-free devices which generate picture languages consisting of collages--sets of parts, where a part is a set of points in a given space. in order to show that certain collage languages cannot be generated, the well-known pumping technique turns out to be rather useless. to circumvent this difficulty, other necessary criteria for context-freeness are established in this paper. roughly speaking, these criteria reveal that (1) the collages in a context-free collage language can be deflated stepwise in such a manner that the difference between subsequent collages in the resulting chain is small and (2) the volume of parts can grow or shrink only exponentially.
on the complexity of recognizing the hilbert basis of a linear diophantine system. the problem of computing the hilbert basis of a homogeneous linear diophantine system over nonnegative integers is often considered in automated deduction and integer programming. in automated deduction, the hilbert basis of a corresponding system serves to compute the minimal complete set of associative-commutative unifiers, whereas in integer programming the hilbert bases are tightly connected to integer polyhedra and to the notion of total dual integrality. in this paper, we sharpen the previously known result that the problem, asking whether a given solution belongs to the hilbert basis of a given system, is conp-complete. we show that the problem has a pseudopolynomial algorithm if the number of equations in the system is fixed, but it is conp-complete in the strong sense if the given system is unbounded. this result is important in the scope of automated deduction, where the input is given in unary and therefore the previously known conp-completeness result was unusable. moreover, we show that, from the complexity standpoint, it is not important to know the underlying homogeneous linear diophantine system when we ask whether a given set of vectors constitutes a hilbert basis.
the variance of the height of binary search trees. by using analytic tools it is shown that the variance e(hnehn)2 of the height hn of binary search trees of size n is bounded.
subtractive reductions and complete problems for counting complexity classes. we introduce and investigate a new type of reductions between counting problems, which we call subtractive reductions. we show that the main counting complexity classes #p, #np, as well as all higher counting complexity classes # ċ πkp, k ≥ 2, are closed under subtractive reductions. we then pursue problems that are complete for these classes via subtractive reductions. we focus on the class #np (which is the same as the class # ċ conp) and show that it contains natural complete problems via subtractive reductions, such as the problem of counting the minimal models of a boolean formula in conjunctive normal form and the problem of counting the cardinality of the set of minimal solutions of a homogeneous system of linear diophantine inequalities.
on robson's convergence and boundedness conjectures concerning the height of binary search trees. let cn denote the number of nodes in a random binary search tree (of n nodes) at the maximal level. in this paper we present a direct proof of robson's boundedness conjecture saying that the expected values e cn remain bounded as n → ∞. we also prove that e cn is asymptotically (multiplicatively) periodic which shows that robson's convergence conjecture (that is, e cn is convergent) is only true if the limiting periodic function c˜(x) is constant. interestingly, it can be shown that c˜(x) is almost constant in the sense that possible oscillations are very small. however, it seems to be a difficult problem to decide whether c˜(x) is really constant or not.we present similar properties for the variance of the height var hn, too.
do stronger definitions of randomness exist? in this paper, we investigate refined definition of random sequences. classical definitions (martin-löf tests of randomness, uncompressibility, unpredictability, or stochasticness) make use of the notion of algorithm. we present alternative definitions based on set theory and explain why they depend on the model of zfc that is considered. we also present a possible generalization of the definition when small infinite regularities are allowed.
comparison between the complexity of a function and the complexity of its graph. this paper investigates in terms of kolmogorov complexity the differences between the information necessary to compute a recursive function and the information contained in its graph. our first result is that the complexity of the initial parts of the graph of a recursive function, although bounded, has almost never a limit. the second result is that the complexity of these initial parts approximate the complexity of the function itself in most cases (and in the average) but not always.
descriptive complexity of computable sequences. our goal is to study the complexity of infinite binary recursive sequences. we introduce several measures of the quantity of information they contain. some measures are based on size of programs that generate the sequence, the others are based on the kolmogorov complexity of its finite prefixes. the relations between these complexity measures are established. the most surprising among them are obtained using a specific two-players game2.
a generic causal model for place latency. for a prototypical class of time-extended petri nets it is shown that the extension does not increase their expressive power. the nets in this class have token latencies attributed to places. place latency nets are formally defined together with their firing semantics. for any place latency system, an explicit construction of an elementary net system is given as an implementation, which is proven to be behaviourally equivalent. the adequacy problem of deciding which equivalence notion to apply is moderated by the fact that the implementation satisfies the b-condition, under which all better known equivalence notions coincide.
on the analysis of the (1+1) evolutionary algorithm. many experimental results are reported on all types of evolutionary algorithms but only few results have been proved. a step towards a theory on evolutionary algorithms, in particular, the so-called (1+1) evolutionary algorithm, is performed. linear functions are proved to be optimized in expected time o(nlnn) but only mutation rates of size (1/n) can ensure this behavior. for some polynomial of degree 2 the optimization needs exponential time. the same is proved for a unimodal function. both results were not expected by several other authors. finally, a hierarchy result is proved. moreover, methods are presented to analyze the behavior of the (1+1) evolutionary algorithm.
optimization with randomized search heuristics - the (a)nfl theorem, realistic scenarios, and difficult functions. the no free lunch (nfl) theorem due to wolpert and macready (ieee trans. evol. comput. 1(1) (1997) 67) has led to controversial discussions on the usefulness of randomized search heuristics, in particular, evolutionary algorithms. here a short and simple proof of the nfl theorem is given to show its elementary character. moreover, the proof method leads to a generalization of the nfl theorem. afterwards, realistic complexity theoretical-based scenarios for black box optimization are presented and it is argued why nfl theorems are not possible in such situations. however, an almost no free lunch (anfl) theorem shows that for each function which can be optimized efficiently by a search heuristic there can be constructed many related functions where the same heuristic is bad. as a consequence, search heuristics use some idea how to look for good points and can be successful only for functions "giving the right hints". the consequences of these theoretical considerations for some well-known classes of functions are discussed.