waashk/dblp huggingface dataset:
shuffle on trajectories: syntactic constraints. we introduce and investigate new methods to define parallel composition of words and languages. the operation of parallel composition leads to new shuffle-like operations defined by syntactic constraints on the usual shuffle operation. the approach is applicable to concurrency, providing a method to define parallel composition of processes. it is also applicable to parallel computation. the operations are introduced using a uniform method based on the notion of trajectory. as a consequence, we obtain a very intuitive geometrical interpretation of the parallel composition operation. these operations lead in a natural way to a large class of semirings. the approach is amazingly flexible, diverse concepts from the theory of concurrency can be introduced and studied in this framework. for instance, we provide examples of applications to fairness property and to parallelization of non-context-free languages in terms of context-free and even regular languages. this paper concetrates on syntactic constraints. semantic constraints will be dealt with in a forthcoming contribution.
categorical foundations for randomly timed automata. the general theory of randomly timed automata is developed: starting with the practical motivation and presentation of the envisaged notion, the categorical theory of minimization, aggregation, encapsulation, interconnection and realization of such automata is worked out. all these constructions are presented universally: minimization and realization as adjunctions, aggregation as product, interconnection as cartesian lifting, and encapsulation as co-cartesian lifting. stochastic timed automata are shown to be a particular case of randomly timed automata. the notion of stochastic timed automaton is shown to be too restrictive to establish a self contained theory of combination and realization.
decision problems for semi-thue systems with a few rules. we show that the accessibility problem, the common descendant problem, the termination problem and the uniform termination problem are undecidable for 3-rules semi-thue systems. as a corollary we obtain the undecidability of the post correspondence problem for 7 rules.
linear programs in a simple reversible language. very simple reversible programming languages can be useful for the study of reversible transformations. for this purpose we define simple reversible language (srl), a very simple reversible language, and analyse its properties. the language srl is similar to the "loop" languages that have been used by several authors to characterise the set of primitive recursive functions. there are, however, important differences: srl has domain z instead of n and only reversible programs can be written in srl. the reversibility of linear homogeneous srl programs is related to the fact that the corresponding set of matrices has the algebraic structure of a group. we show that such programs implement exactly the linear transformations corresponding to the group of integer positive modular matrices, while in esrl, an extended version of srl, the set of transformations that can be implemented by linear homogeneous programs corresponds exactly to the group of integer modular matrices.
np-completeness for calculating power indices of weighted majority games. in this paper, we prove that both problems for calculating the banzhaf power index and the shapley-shubik power index for weighted majority games are np-complete.
the accepting power of unary string logic programs. the set of programs written in a small subset of pure prolog called us is shown to accept exactly the class of regular languages. the language us contains only unary predicates and unary function symbols. also, a subset of us called rus is shown to be equivalent to us in its ability in accepting the class of regular languages. every clause in rus contains at most one function symbol in the head and at most one literal with no function symbol in the body. the result is very close to a theorem of matos (tcs april 1997) but our proof is quite different. though us and rus have the same accepting power, their conciseness of expression is dramatically different: if we try to write an rus program equivalent to a us program, the number of predicates in the rus program could be o(22n2) where n is the sum of the number of predicates and the number of functors in the us program. copyright 2001 elsevier science b.v.
substitution in non-wellfounded syntax with variable binding. inspired from the recent developments in theories of non-wellfounded syntax (coinductively defined languages) and of syntax with binding operators, the structure of algebras of wellfounded and non-wellfounded terms is studied for a very general notion of signature permitting both simple variable binding operators as well as operators of explicit substitution. this is done in an extensional mathematical setting of initial algebras and final coalgebras of endofunctors on a functor category. the main technical tool is a novel concept of heterogeneous substitution systems.
an extensional treatment of lazy data flow deadlock. in an extensional treatment of dataflow deadlock [wa81] wadge introduced an elegant non operational test for proving that many of kahn''s data flow message passing networks [ka74] must be free of deadlock; a test that "should extend to a much wider context" in the study of program correctness. such a context has now been provided with the introduction of partial metric spaces [ma92]. these spaces can be used to describe semantic domains such as those used in lazy data flow languages [w &a85]. this paper develops wadge''s ideas on establishing an extensional theory of program correctness by using partial metric spaces to give a non operational treatment of lazy data flow deadlock. the acm portal is published by the association for computing machinery. copyright © 2010 acm, inc. terms of usage privacy policy code of ethics contact us useful downloads: adobe acrobat quicktime windows media player real player
dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures. this paper presents results from two different areas. the first area is monadic second-order logic (mso) over finite structures, in particular over the so-called grids. these are structures whose elements can be arranged as a matrix and which have two binary relations corresponding to vertical and horizontal successors. for this logic, we study the expressive power of the alternation of existential and universal monadic second-order quantifiers, i.e., set quantifiers. in matz et al. (information and computation, lics' 97, 1999, to appear) it had been shown that these alternations cannot be limited to a fixed number without loss of expressiveness. in this paper, we strengthen this result in several ways. firstly, we show that there are mso formulas that have a very restricted form of k+1 set quantifiers but are not equivalent to a formula with k quantifiers. secondly, we show that if we fix the number of such alternations, the expressive power of formulas that start with a block of universal quantifiers differs from the power of those that start with an existential one this was previously known only for coloured grids. thirdly, we investigate how an additional prefix of first-order (i.e., element) quantifiers influences the expressive power of mso formulas. the second area that this paper is concerned with is two-dimensional formal language theory. we study how the alternation of (first- and monadic second-order) quantifications, on the one hand, relates to the dot-depth measure of two-dimensional (i.e., picture) languages, on the other hand. that measure is the two-dimensional version of the classical notion of dot-depth for (one-dimensional) starfree word languages. we show that the hierarchy induced by this dot-depth cuts through the hierarchy given by monadic second-order quantifications. in particular, beyond each level of the monadic second-order alternation hierarchy, there is a starfree picture language.
finite and infinite pseudorandom binary words. we present a notion of pseudorandomness for finite binary words based on the measure of the well distribution in arithmetic progressions and of the correlations. we give several examples and we focuss our interest on two arithmetical constructions connected to the legendre symbol and the liouville function.
the syntactic prediction with token automata: application to handias system. this paper presents a finite-state machine to compute the probability of a word appearance when one knows the left syntactic context. we memorize the token number of words in a dictionary and the token number of syntactic categories on finite-state automata. we compute a word probability with these numbers. if we have not predicted the awaited word , we take into account the first letter for a new prediction, and so on. this system has been implemented on a prototype software for disabled communication aid, called handias and it is a part of the research project cnhl of the li, the computer laboratory of the tours university. copyright 2001 elsevier science b.v.
algorithms for pattern matching and discovery in rna secondary structure. text-indexing structures provide significant advantages in the solution of many problems related to string analysis and comparison, and are nowadays widely used in the analysis of biological sequences. in this paper, we present some applications of affix trees to problems of exact and approximate pattern matching and discovery in rna sequences. by allowing bidirectional search for symmetric patterns in the sequences, affix trees permit to discover and locate in the sequences patterns describing not only sequence regions, but also containing information about the secondary structure that a given region could form, with improvements in terms of theoretical and practical efficiency over the existing methods. the search can be either exact or approximate, where the approximation can be defined simultaneously both for the sequence and the structure of patterns. the approach presented in this paper could provide significant help in the analysis of rna sequences, where the functional motifs often involve not only sequence, but also the structural constraints.
trade-off results for connection management. a connection management protocol establishes and handles a connection between two hosts across a wide-area network to allow reliable message delivery. we continue the previous work of kleinberg et al. (proceedings of the 3rd israel symposium on the theory of computing and systems, january (1995), pp. 258-267) to study the precise impact of the level of synchrony provided by the processors' clocks on the performance of connection management protocols, under common assumptions on the pattern of failures of the network and the host nodes. two basic timing models are assumed: clocks that exhibit a certain kind of a drift from the rate of real time, and clocks that display a pattern of synchronization to real time. we consider networks that can duplicate and reorder messages, and nodes that can crash. we are interested in simultaneously optimizing the following performance parameters: the message delivery time, which is the time required to deliver a message, and the quiescence time, which is the time that elapses between periods of quiescence, in which the receiving host deletes all earlier connection records and returns to an initial state. we establish natural trade-offs between message delivery time and quiescence time, in the form of tight lower and upper bounds, for each combination of the timing models and failure types. several of our trade-off results significantly improve upon or extend previous ones shown by kleinberg et al.
weak bisimilarity and regularity of context-free processes is exptime-hard. we show that checking weak bisimulation equivalence of two context-free processes (also called bpa-processes) is exptime-hard, even under the condition that the processes are normed. furthermore, checking weak regularity (finiteness up to weak bisimilarity) for context-free processes is exptime-hard as well. adding a finite control of the minimal non-trivial size of 2 to the bpa process already makes weak bisimilarity undecidable.
encoding transition systems in sequent calculus. intuitionistic and linear logics can be used to specify the operational semantics of transition systems in various ways. we consider here two encodings: one uses linear logic and maps states of the transition system into formulas, and the other uses intuitionistic logic and maps states into terms. in both cases, it is possible to relate transition paths to proofs in sequent calculus. in neither encoding, however, does it seem possible to capture properties, such as simulation and bisimulation, that need to consider all possible transitions or all possible computation paths. we consider augmenting both intuitionistic and linear logics with a proof theoretical treatment of definitions. in both cases, this addition allows proving various judgments concerning simulation and bisimulation (especially for noetherian transition systems). we also explore the use of infinite proofs to reason about infinite sequences of transitions. finally, combining definitions and induction into sequent calculus proofs makes it possible to reason more richly about properties of transition systems completely within the formal setting of sequent calculus.
quantitative program logic and expected time bounds in probabilistic distributed algorithms. in this paper we show how quantitative program logic (morgan et al., acm trans. programming languages systems 18 (1996) 325) provides a formal framework in which to promote standard techniques of program analysis to a context where probability and nondeterminism interact, a situation common to probabilistic distributed algorithms. we show that overall expected time can be formulated directly in the logic and that it can be derived from local properties of components. we illustrate the methods with an analysis of expected running time of the probabilistic dining philosophers (lehmann and ravin, proc 8th annu. acm. symp. on principles of programming languages, acm, new york, 1981, p. 133).
partial correctness for probabilistic demonic programs. recent work in sequential program semantics has produced both an operational (he et al., sci. comput. programming 28(2, 3) (1997) 171-192) and an axiomatic (morgan et al., acm trans. programming languages systems 18(3) (1996) 325-353; seidel et al., tech report prg-tr-6-96, programming research group, february 1996) treatment of total correctness for probabilistic demonic programs, extending kozen's original work (j. comput. system sci. 22 (1981) 328-350; kozen, proc. 15th acm symp. on theory of computing, acm, new york, 1983) by adding demonic nondeterminism. for practical applications (e.g. combining loop invariants with termination constraints) it is important to retain the traditional distinction between partial and total correctness. jones (monograph ecs-lfcs-90-105, ph.d. thesis, edinburgh university, edinburgh, uk, 1990) defines probabilistic partial correctness for probabilistic, but again not demonic programs. in this paper we combine all the above, giving an operational and axiomatic framework for both partial and total correctness of probabilistic and demonic sequential programs; among other things, that provides the theory to support our earlier---and practical---publication on probabilistic demonic loops (morgan, in: jifeng et al. (eds.), proc. bcs-facs seventh refinement workshop, workshops in computing, springer, berlin, 1996. copyright 2001 elsevier science b.v.
almost-certain eventualities and abstract probabilities in the quantitative temporal logic qtl. 'almost-certain eventualities' are liveness properties that hold with probability 1. 'abstract probabilities' in transition systems are those known only to be bounded away from zero and one.vardi (proceedings of the 26th ieee symposium on foundations of computer science, portland, 1985, p. 327) showed that almost-certain properties in linear temporal logic depend only on abstract probabilities rather than on the probabilities' precise values. we discuss the extent to which a similar result holds in the quantitative temporal logic qtl derived from the quantitative modal µ,calculus qmµ (proceedings the formal methods pacific '97, springer, singapore, 1997, also available http://web.comlab.ox.ac.uk/oucl/research/areas/probs/bibliography.html; logic j, igpl 7(6) (1999) 779, http://www3.oup.co.uk/igpl/volume_07/issue_06, http://web.comlab. ox.ac.uk/oucl/research/areas/probs/bibliography.html), and we show how to specialise the logic to these cases. the aim is to provide a simpler calculus than the full logic, one that is in a certain sense complete for proving almost-certain eventualities from abstract-probabilistic assumptions.we concinde by considering the complexity of the specialised logic.
an interpolating theorem prover. we present a method of deriving craig interpolants from proofs in the quantifier-free theory of linear inequality and uninterpreted function symbols, and an interpolating theorem prover based on this method. the prover has been used for predicate refinement in the blast software model checker, and can also be used directly for model checking infinite-state systems, using interpolation-based image approximation.
the generative capacity of block-synchronized context-free grammars. we consider the yield languages of synchronized tree automata, called the synchronized context-free (scf) languages. we show that their language family coincides with the family of etol languages using both studied types of synchronization. furthermore, we examine a generalization of scf grammars, the block-synchronized context-free (bscf) grammars and determine that their generated language family is equal to that of the indexed languages using the same two types of synchronization. however, when the nesting depth of bscf grammars is bounded above by some constant, the generated language family is also equal to the family of et0l languages. this shows that the unbounded nesting depth language family is strictly larger than the bounded nesting depth family, as previously conjectured.
decision tree approximations of boolean functions. decision trees are popular representations of boolean functions. we show that, given an alternative representation of a boolean function f, say as a read-once branching program, one can find a decision tree t which approximates f to any desired amount of accuracy. moreover, the size of the decision tree is at most that of the smallest decision tree which can represent f and this construction can be obtained in quasi-polynomial time. we also extend this result to the case where one has access only to a source of random evaluations of the boolean function f instead of a complete representation. in this case, we show that a similar approximation can be obtained with any specified amount of confidence (as opposed to the absolute certainty of the former case.) this latter result implies proper pac-learnability of decision trees under the uniform distribution without using membership queries.
extended games-chan algorithm for the 2-adic complexity of fcsr-sequences. binary sequences generated by feedback shift registers with carry operation (fcsr) share many of the important properties enjoyed by sequences generated by linear feedback shift registers. we present an fcsr analog of the (extended) games-chan algorithm, which efficiently determines the linear complexity of a periodic binary sequence with period length t = 2n or pn, where p is an odd prime and 2 is a primitive element modulo p2. the algorithm to be presented yields an upper bound for the 2-adic complexity, an fcsr analog of the linear complexity, of a pn-periodic binary sequence.
a time lower bound for satisfiability. we show that a deterministic turing machine with one d-dimensional work tape and random access to the input cannot solve satisfiability in time na for a < √(d + 2)/(d + 1). for conondeterministic machines, we obtain a similar lower bound for any a such that a3 < 1 + a/(d + 1). the same bounds apply to almost all natural np-complete problems known.
sequential algorithms and strongly stable functions. intuitionistic proofs and pcf programs may be interpreted as functions between domains, or as strategies on games. the two kinds of interpretation are inherently different: static vs. dynamic, extensional vs. intentional. it is thus extremely instructive to compare and to connect them. in this article, we investigate the extensional content of the sequential algorithm hierarchy [-]sds introduced by berry and curien. we equip every sequential game [t]sds of the hierarchy with a realizability relation between plays and extensions. in this way, the sequential game [t]sds becomes a directed acyclic graph, instead of a tree. this enables to define a hypergraph [t]hc on the extensions (or terminal leaves) of the game [t]sds. we establish that the resulting hierarchy [-]hc coincides with the strongly stable hierarchy introduced by bucciarelli and ehrhard. we deduce from this a gametheoretic proof of ehrhard's collapse theorem, which states that the strongly stable hierarchy coincides with the extensional collapse of the sequential algorithm hierarchy.
asynchronous games 2: the true concurrency of innocence. in game semantics, the higher-order value passing mechanisms of the λ-calculus are decomposed as sequences of atomic actions exchanged by a player and its opponent. seen from this angle, game semantics is reminiscent of trace semantics in concurrency theory, where a process is identified to the sequences of requests it generates in the course of time. asynchronous game semantics is an attempt to bridge the gap between the two subjects, and to see mainstream game semantics as a refined and interactive form of trace semantics. asynchronous games are positional games played on mazurkiewicz traces, which reformulate (and generalize) the familiar notion of arena game. the interleaving semantics of λ-terms, expressed as innocent strategies, may be analysed in this framework, in the perspective of true concurrency. the analysis reveals that innocent strategies are positional strategies regulated by forward and backward confluence properties. this captures, we believe, the essence of innocence. we conclude the article by defining a non-uniform variant of the λ-calculus, in which the game semantics of a λ-term is formulated directly as a trace semantics, performing the syntactic exploration or parsing of that λ-term.
components as coalgebras: the refinement dimension. this paper characterises refinement of state-based software components modelled as pointed coalgebras for some set endofunctors. the proposed characterisation is parametric on a specification of the underlying behaviour model introduced as a strong monad. this provides a basis to reason about (and transform) state-based software designs. in particular, it is shown how refinement can be applied to the development of the inequational subset of a calculus of generic software components.
complementing unary nondeterministic automata. we compare the nondeterministic state complexity of unary regular languages and that of their complements: if a unary language l has a succinct nondeterministic finite automaton, then nondeterminism is useless in order to recognize its complement, namely, the smallest nondeterministic automaton accepting the complement of l has as many states as the minimum deterministic automaton accepting it. the same property does not hold in the case of automata and languages defined over larger alphabets. we also show the existence of infinitely many unary regular languages for which nondeterminism is useless in their recognition and in the recognition of their complements.