waashk/dblp huggingface dataset:
casl: the common algebraic specification language. the common algebraic specification language (casl) is an expressive language for the formal specification of functional requirements and modular design of software. it has been designed by cofi, the international common framework initiative for algebraic specification and development. it is based on a critical selection of features that have already been explored in various contexts, including subsorts, partial functions, first-order logic, and structured and architectural specifications. casl should facilitate interoperability of many existing algebraic prototyping and verification tools.this paper gives an overview of the casl design. the major issues that had to be resolved in the design process are indicated, and all the main concepts and constructs of casl are briefly explained and illustrated -- the reader is referred to the casl language summary for further details. some familiarity with the fundamental concepts of algebraic specification would be advantageous.
algebraic aspects of families of fuzzy languages. we study operations on fuzzy languages such as union, concatenation, kleene *, intersection with regular fuzzy languages, and several kinds of (iterated) fuzzy substitution. then we consider families of fuzzy languages, closed under a fixed collection of these operations, which results in the concept of full abstract family of fuzzy languages or full affl. this algebraic structure is the fuzzy counterpart of the notion of full abstract family of languages that has been encountered frequently in investigating families of crisp (i.e., non-fuzzy) languages. some simpler and more complicated algebraic structures (such as full substitution-closed affl, full super-affl, full hyper-affl) will be considered as well.in the second part of the paper we focus our attention to full affls closed under iterated parallel fuzzy substitution, where the iterating process is prescribed by given crisp control languages. proceeding inductively over the family of these control languages, yields an infinite sequence of full affl-structures with increasingly stronger closure properties.
fuzzy context-free languages - part 1: generalized fuzzy context-free grammars. motivated by aspects of robustness in parsing a context-free language, we study generalized fuzzy context-free grammars. these fuzzy context-free k-grammars provide a general framework to describe correctly as well as erroneously derived sentences by a single generating mechanism. they model the situation of making a finite choice out of an infinity of possible grammatical errors during each context-free derivation step. formally, a fuzzy context-free k-grammar is a fuzzy context-free grammar with a countable rather than a finite number of rules satisfying the following condition: for each symbol α, the set containing all right-hand sides of rules with left-hand side equal to α forms a fuzzy language that belongs to a given family k of fuzzy languages. we investigate the generating power of fuzzy context-free k-grammars, and we show that under minor assumptions on the parameter k, the family of languages generated by fuzzy context-free k-grammars possesses closure properties very similar to those of the family of ordinary context-free languages.
fuzzy context-free languages - part 2: recognition and parsing algorithms. in a companion paper [p.r.j. asveld, fuzzy context-free languages--part 1: generalized fuzzy context-free grammars, theoret. comput. sci. (2005)] we used fuzzy context-free grammars in order to model grammatical errors resulting in erroneous inputs for robust recognizing and parsing algorithms for fuzzy context-free languages. in particular, this approach enables us to distinguish between small errors ("tiny mistakes") and big errors ("capital blunders").in this paper, we present some algorithms to recognize fuzzy context-free languages: particularly, a modification of cocke-younger-kasami's algorithm and some recursive descent algorithms. then we extend these recognition algorithms to corresponding parsing algorithms for fuzzy context-free languages. these parsing algorithms happen to be robust in some very elementary sense.
generating all permutations by context-free grammars in chomsky normal form. let ln be the finite language of all n! strings that are permutations of n different symbols (n ≥ 1). we consider context-free grammars gn in chomsky normal form that generate ln. in particular we study a few families {gn}n ≥ 1, satisfying l(gn) = ln for n ≥ 1, with respect to their descriptional complexity, i.e. we determine the number of nonterminal symbols and the number of production rules of gn as functions of n.
sorting with two ordered stacks in series. the permutations that can be sorted by two stacks in series are considered, subject to the condition that each stack remains ordered. a forbidden characterisation of such permutations is obtained and the number of permutations of each length is determined by a generating function.
improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms. we show that the known bounded-depth proofs of the weak pigeonhole principle phpn2n in size no(log(n)) are not optimal in terms of size. more precisely, we give a size-depth trade-off upper bound: there are proofs of size no(d(log(n))2/d) and depth o(d). this solves an open problem of maciel et al. (proceedings of the 32nd annual acm symposium on the theory of computing, 2000). our technique requires formalizing the ideas underlying nepomnjascij's theorem which might be of independent interest. moreover, our result implies a proof of the unboundedness of primes in iδ0 with a provably weaker 'large number assumption' than previously needed.
linear time approximation schemes for vehicle scheduling problems. we consider makespan minimization for vehicle scheduling problems on trees with job requests that have release and handling times. 2-approximation algorithms were known for several variants of the single vehicle problem on a path. a 3/2-approximation algorithm was known for the single vehicle problem on a path where there is a fixed starting point and the vehicle must return to the starting point upon completion. karuno, nagamochi and ibaraki give a 2-approximation algorithm for the single vehicle problem on trees. we develop a polynomial time approximation scheme (ptas) that runs in time linear in the number of job requests for the single vehicle scheduling problem on trees that have a constant number of leaves. this ptas can be easily adapted to accommodate various starting/ending constraints. we then extended this to a ptas for the multiple vehicle problem where vehicles operate in disjoint subtrees.
constructing divisions into power groups. the result, due to henckell, margolis, pin and rhodes modulo ash's solution to the pointlike conjecture, that every finite block group divides a power group, has long been considered to be one of the deepest results in finite semigroup and algebraic automata theory. however, the proof is not constructive. solving a long-standing problem, we provide in this paper an explicit construction of such a division. we also generalize the result to a large class of pseudovariefies of groups. local group pseudovarieties are also considered, generalizing (and making constructive) results of margolis and the second author. some applications to language theory are mentioned.
sparse and limited wavelength conversion in all-optical tree networks. we study the problem of assigning a minimum number of colors to directed paths (dipaths) if a tree, so that any two dipaths that share a directed edge of the tree are not assigned the same color. the problem has applications to wavelength routing in wdm all-optical tree networks, an important engineering problem. dipaths represent communication requests, while colors correspond to wavelengths that must be assigned to requests so that multiple users can communicate simultaneously through the same optical fiber. recent work on wavelength routing in trees has studied a special class of algorithms which are called greedy. although these algorithms are simple and implementable in a distributed setting, it has been proved that there are cases where a bandwidth utilization of 100% is not possible. thus, in this work, we relax the constraints of the original engineering problem and use devices called wavelength converters that are able to convert the wavelength assigned to a segment of a communication request to another wavelength that will be assigned to some other segment of the same request. the trade-off of the use of wavelength converters is increased cost and complexity; so, our aim is to use converters that have relatively simple functionality. we study the performance of greedy deterministic algorithms in tree-shaped all-optical networks that support wavelength conversion. we study both the case of sparse conversion and limited conversion. by sparse we mean that converters have full conversion capabilities and the objective is to minimize the number of converters employed. on the other hand, in limited conversion, we assume that converters with limited conversion capabilities are placed at each non-leaf node of the tree. by limited, we mean that converters are simple according to either their wavelength degree or their size. our results show that using converters of either low degree or small size, we can beat the known lower bounds and improve bandwidth utilization. in some cases we even achieve optimal bandwidth utilization. for the construction of the converters, we use special classes of graphs such as expanders, dispersers and depth-two superconcentrators. explicit constructions are known for most of the graphs used in this paper. copyright 2001 elsevier science b.v.
randomized path coloring on binary trees. motivated by the problem of wdm routing in all-optical networks, we study the following np-hard problem. we are given a directed binary tree t and a set r of directed paths on t. we wish to assign colors to paths of r, in such way that no two paths that share a directed arc of t are assigned the same color, and the total number of colors used is minimized. our results are expressed in terms of the depth of the tree and of the maximum load l of r, i.e. the maximum number of paths that go through a directed arc of t. so far, only deterministic greedy algorithms have been presented for the problem. the best known algorithm colors any set r of maximum load l using at most 5l/3 colors. alternatively, we say that this algorithm has performance ratio 5/3. it is also known that no deterministic greedy algorithm can achieve a performance ratio better than 5/3. in this paper we define the class of greedy algorithms that use randomization. we study their limitations and prove that, with high probability, randomized greedy algorithms cannot achieve a performance ratio better than 3/2 when applied for binary trees of depth ω(l), and 1.293-o(1) when applied for binary trees of constant depth. exploiting inherent properties of randomized greedy algorithms, we obtain the first randomized algorithm for the problem that uses at most 7l/5 + o(l) colors for coloring any set of paths of maximum load l on binary trees of depth o(l1/3-ε), with high probability. we also present an existential upper bound of 7l/5 + o(l) that holds on any binary tree. for the analysis of our bounds we develop tail inequalities for random variables following hypergeometrical probability distributions that might be of their own interest.
clock construction in fully asynchronous parallel systems and pram simulation. the authors discuss the question of simulating synchronous computations on asynchronous systems. they consider an asynchronous system with very weak, or altogether lacking any, atomicity assumptions. the first contribution of this paper is a novel clock for asynchronous systems. the clock is a basic tool for synchronization in the asynchronous environment. it is a very robust construction and can operate in a system with no atomicity assumptions, and in the presence of a dynamic scheduler. the behavior of the clock is obtained with overwhelming probability (1-2/sup - alpha n/, alpha >0). the authors show how to harness this clock to drive a pram simulation on an asynchronous system. the resulting simulation scheme is more efficient than existing ones, while actually relaxing the assumptions on the underlying asynchronous system.
approximating uniform triangular meshes in polygons. we consider the problem of triangulating a convex polygon using n steiner points under the following optimality criteria: (1) minimizing the overall edge length ratio; (2) minimizing the maximum edge length; and (3) minimizing the maximum triangle perimeter. we establish a relation of these problems to a certain extreme packing problem. based on this relationship, we develop a heuristic producing constant approximations for all the optimality criteria above (provided n is chosen sufficiently large). that is, the produced triangular mesh is uniform in these respects.the method is easy to implement and runs in o(n2log n) time and o(n) space. the observed runtime is much less. moreover, for criterion (1) the method works--within the same complexity and approximation bounds--for arbitrary polygons with possible holes, and for criteria (2) and (3) it does so for a large subclass.
a structural property of regular frequency computations. the notion of an (m,n)-computation was already introduced in 1960 by rose and further investigated by trakhtenbrot in 1963. it has been extended to finite automata by kinber in 1976 and he has shown an analogue of trakhtenbrot's result: the class of languages (m,n)-recognizable by deterministic finite automata is equal to the class of regular languages if and only if 2m > n. furthermore, for a unary alphabet, the class of (m,n)-recognizable languages coincides with the class of regular languages for all m and n. in this paper, we will present the first structural property of (m,n)-recognizable languages which is valid for all 1 ≤ m ≤ n and for all alphabets. kinber's result for unary alphabets becomes a corollary. this property is also used to show that certain non-unary languages are not (m,n)-regular and that the class of all (m,n)-recognizable languages is not closed under the reversal operation. however, this class forms a boolean algebra.
regular frequency computations. an (m, n)-computation of a function f is given by a deterministic turing machine which on n pairwise different inputs produces n output values where at least m of the n values are in accordance with f. in such a case, we say that the turing machine computes f with frequency ≥ m/n. the most prominent result for frequency computations is due to trakhtenbrot: the class of (m, n)-computable functions equals the class of computable functions if and only if 2m > n.via characteristic functions the definition of (m, n)-computability carries over to sets. here trakhtenbrot's result reads as: the class of (m, n)-computable sets equals the class of recursive sets if and only if 2m > n.the notion of frequency computation can be extended to other models of computation. for resource bounded computations, the behavior is completely different: for e.g., whenever n' - m' > n - m, it is known that under any reasonable resource bound there are sets (m', n')-computable, but not (m, n)- computable.however, scaling down to finite automata, the analogue of trakhtenbrot's result holds again: we show here that the class of languages (m, n)-recognizable by deterministic finite automata equals the class of regular languages if and only if 2m > n. this was originally stated by kinber, but his proof has a flaw, as pointed out by tantau.conversely, for 2m ≤ n, the class of languages (m, n)-recognizable by deterministic finite automata is uncountable for a two-letter alphabet. when restricted to a one-letter alphabet, then every (m, n)- recognizable language is regular. this was also shown by kinber. we give a new and more direct proof for this result.
tradeoffs in worst-case equilibria. we investigate the problem of routing traffic through a congested network in an environment of non-cooperative users. we use the worst-case coordination ratio suggested by koutsoupias and papadimitriou to measure the performance degradation due to the lack of a centralized traffic regulating authority. we provide a full characterization of the worst-case coordination ratio in the restricted assignment and unrelated parallel links model. in particular, we quantify the tradeoff between the "negligibility" of the traffic controlled by each user and the worst-case coordination ratio. we analyze both pure and mixed strategies systems and identify the range where their performance is similar.
weak lighting functions and strong 26-surfaces. the goal of this paper is to introduce the notion of weak lighting function in order to replicate the "continuous perception" associated with strong 26-surfaces. as a consequence, the continuous analogue defined ad hoc by malgouyres and bertrand only for these surfaces is extended for arbitrary objects, and the local characterization of finite strong 26-surfaces given in (malgouyres and bertrand, int. j. pattern recognition art. intell. 13(4) (1999) 465-484) is generalized to possibly infinite surfaces. moreover, weak lighting functions also replicate the "continuous perception" associated with (,)-surfaces, (,)(6,6), since they are generalizing the lighting functions previously defined by the authors.
decision procedures for inductive boolean functions based on alternating automata. we show how alternating automata provide decision procedures for the equality of inductively defined boolean functions and present applications to reasoning about parameterized families of circuits. we use alternating word automata to formalize families of linearly structured circuits and alternating tree automata to formalize families of tree structured circuits. we provide complexity bounds for deciding the equality of function (or circuit) families and show how our decision procedures can be implemented using bdds. in comparison to previous work, our approach is simpler, has better complexity bounds, and, in the case of tree-structured families, is more general.
on-line load balancing. the setup for the authors' problem consists of n servers that must complete a set of tasks. each task can be handled only by a subset of the servers, requires a different level of service, and once assigned can not be re-assigned. they make the natural assumption that the level of service is known at arrival time, but that the duration of service is not. the on-line load balancing problem is to assign each task to an appropriate server in such a way that the maximum load on the servers is minimized. the authors derive matching upper and lower bounds for the competitive ratio of the on-line greedy algorithm for this problem, namely /sup (3n)2/3///sub 2/(1+o(1)), and derive a lower bound, omega ( square root n), for any other deterministic or randomized on-line algorithm.
load balancing of temporary tasks in the norm. we consider the on-line load balancing problem where there are m identical machines (servers). jobs arrive at arbitrary times, where each job has a weight and a duration. a job has to be assigned upon its arrival to exactly one of the machines. the duration of each job becomes known only upon its termination (this is called temporary tasks of unknown durations). once a job has been assigned to a machine it cannot be reassigned to another machine. the goal is to minimize the maximum over time of the sum (over all machines) of the squares of the loads, instead of the traditional maximum load.minimizing the sum of the squares is equivalent to minimizing the load vector with respect to the l2 norm. we show that for the l2 norm the greedy algorithm performs within at most 1.493 of the optimum. we show (an asymptotic) lower bound of 1.33 on the competitive ratio of the greedy algorithm. we also show a lower bound of 1.20 on the competitive ratio of any algorithm.we extend our techniques and analyze the competitive ratio of the greedy algorithm with respect to the lp norm. we show that the greedy algorithm performs within at most 2 - ω(1/p) of the optimum. we also show a lower bound of 2 - o(in p/p) on the competitive ratio of any on-line algorithm.
an improved algorithm for online coloring of intervals with bandwidth. we present an improved online algorithm for coloring interval graphs with bandwidth. this problem has recently been studied by adamy and erlebach and a 195-competitive online strategy has been presented. we improve this by presenting a 10-competitive strategy. to achieve this result, we use variants of an optimal online coloring algorithm due to kierstead and trotter.
on-line bin-stretching. we are given a sequence of items that can be packed into m unit size bins. in the classical bin packing problem we fix the size of the bins and try to pack the items in the minimum number of such bins. in contrast, in the bin-stretching problem we fix the number of bins and try to pack the items while stretching the size of the bins as least as possible. we present two on-line algorithms for the bin-stretching problem that guarantee a stretching factor of 5/3 for any number m of bins. we then combine the two algorithms and design an algorithm whose stretching factor is 1:625 for any m. the analysis for the performance of this algorithm is tight. the best lower bound for any algorithm is 4/3 for any m&ge;2. we note that the bin-stretching problem is also equivalent to the classical scheduling (load balancing) problem in which the value of the makespan (maximum load) is known in advance. copyright 2001 elsevier science b.v.
off-line temporary tasks assignment. in this paper we consider the temporary tasks assignment problem. in this problem, there are m parallel machines and n independent jobs. each job has an arrival time, a departure time and some weight. each job should be assigned to one machine. the load on a machine at a certain time is the sum of the weights of jobs assigned to it at that time. the objective is to find an assignment that minimizes the maximum load over machines and time.we present a polynomial time approximation scheme for the case in which the number of machines is fixed. we also show that for the case in which the number of machines is given as part of the input (i.e., not fixed), no polynomial algorithm can achieve a better approximation ratio than 3/2 unless p = np.