waashk/dblp huggingface dataset:
algorithmic complexity of recursive and inductive algorithms. the main goal of this paper is to compare recursive algorithms such as turing machines with such super-recursive algorithms as inductive turing machines. this comparison is made in a general setting of dual complexity measures such as kolmogorov or algorithmic complexity. to make adequate comparison, we reconsider the standard axiomatic approach to complexity of algorithms. the new approach allows us to achieve a more adequate representation of static system complexity in the axiomatic context. it is demonstrated that for solving many problems inductive turing machines have much lower complexity than turing machines and other recursive algorithms. thus, inductive turing machines are not only more powerful, but also more efficient than turing machines.
experience, generations, and limits in machine learning. this paper extends traditional models of machine learning beyond their one-level structure by introducing previously obtained problem knowledge into the algorithm or automaton involved. some authors studied more advanced than traditional models that utilize some kind of predetermined knowledge, having a two-level structure. however, even in this case, the model has not reflected the source and inherited properties of predetermined knowledge. in society, knowledge is often transmitted from previous generations. the aim of this paper is to construct and study algorithmic models of learning processes that utilize predetermined or prior knowledge. the models use recursive, subrecursive, and super-recursive algorithms. predetermined knowledge includes: a text description, activity rules (e.g., for cognition), and specific structured personal or social memory. algorithmic models represent these three forms as separate structured processing systems: automata with (1) advice; (2) structured program; and (3) structured memory. that yields three basic models for learning systems: polynomially bounded turing machines, turing machines, and inductive turing machines of the first order.
threshold counters with increments and decrements. a threshold counter is a shared data structure that assumes integer values. it provides two operations: increment changes the current counter value from v to v+1, while read returns the value [v/w], where v is the current counter value and w is a fixed constant. thus, the read operation returns the "approximate" value of the counter to within the constant w. threshold counters have many potential uses, including software barrier synchronization. threshold networks are a class of distributed data structures that can be used to construct highly-concurrent, low-contention implementations of shared threshold counters. in this paper, we give the first proof that any threshold network construction of a threshold counter can be extended to support a decrement operation that changes the counter value from v to v ---1.
analysis issues in petri nets with inhibitor arcs. we investigate the problem of extending the analysis techniques developed for p/t systems to a proper subclass of p/t systems with inhibitor arcs. we start proposing an extension of the coverability tree construction to a subclass of p/t systems with inhibitor arcs, whose elements will be called henceforth primitive systems. we show that the coverability tree corresponding to a primitive system is finite and is a good representation of its behaviour; hence, it can be used as an analysis tool to check properties such as place boundedness, the existence of dead transitions and of a reachable marking larger than a given one. then we provide an encoding of primitive systems in p/t systems, which permits to retrieve the firing sequences of the primitive system from the firing sequences of the corresponding p/t system. the close correspondence between the firing sequences of the two systems is used prove the decidability of reachability, deadlock and liveness for primitive systems. we also obtain that the model checking problem for the linear time -calculus and labelled primitive systems is decidable. we show that primitive systems coincide with the largest class of p/t systems with inhibitor arcs whose transition sequences can be simulated by a standard p/t system; we also show that in general the step behaviour of a primitive system cannot be simulated by any p/t system. these results are then used to investigate the expressiveness of inhibitor arcs regarding the class of generated languages.
comparing three semantics for linda-like languages. a simple calculus based on generative communication is introduced; among its primitives, it contains a conditional input operation that tests for presence (or absence) of an output, reminiscent of the inp predicate of linda. we study three different operational semantics for the output operation, called instantaneous, ordered and unordered. the associated behavioural semantics are obtained as the coarsest congruence contained in the corresponding strong barbed semantics. we prove that when the output operation is instantaneous, the obtained semantics is a sort of asynchronous bisimulation; on the contrary, for the ordered semantics, as well as for the unordered one, the resulting semantics is a small variant of the classic (synchronous) bisimulation. further rusults are related to the expressiveness of the language. the language is turing powerful under both the instantaneous and ordered semantics, but there exists a series of problems having solution under the instantaneous interpretation that cannot be solved under the ordered one. instead, the language is not turing powerful under the unordered semantics. thus, we conclude that there exists a precise expressiveness hierarchy among the three semantics.
a process algebraic view of linda coordination primitives. the main linda coordination primitives (asynchronous communication, read operation, nonblocking in/rd predicates) are studied in a process algebraic setting. a lattice of eight languages is proposed, where its bottom element l is a process algebra differing from ccs only for the asynchrony of the output operation, while all the other languages in the lattice are obtained as extension of this basic language by adding some of the linda coordination primitives. the observational semantics for these languages are all obtained as the coarsest congruences contained in the barbed semantics, where only tuples are observable. the lattice of the eight languages collapses to a smaller four-points lattice of different bisimulation-based semantics. notably, for l this semantics is the standard notion of strong bisimulation, where inputs and outputs/tuples are treated symmetrically.
expired data collection in shared dataspaces. the shared dataspace metaphor is historically the most prominent representative of the family of coordination models. according to this approach, concurrent processes interact via the production, consumption, and test for presence/absence of data in a common repository. recently, the problem of the accumulation of outdated and unwanted information in the shared repository has been addressed. typical garbage collection algorithms cannot be adopted in this context because there is no notion of unaccessible data. the most promising solution to this problem consists of the introduction of the notion of temporary data, intended as data with an associated expiration time. in this paper, we investigate the impact of different mechanisms for expired data collection on the expressiveness of shared dataspace coordination systems with temporary data.
on the expressive power of movement and restriction in pure mobile ambients. pure mobile ambients is a process calculus suitable to focus on issues related to mobility, abstracting away from aspects concerning process communication. however, it incorporates name restriction (i.e. the (vn) binder) and ambient movement (i.e. the in and out capabilities) that can be seen as characteristics adapted, or directly borrowed, from the tradition of communication-based process calculi. for this reason, we retain that it is worth to investigate whether or not these features can be removed from pure mobile ambients without losing expressive power.to this aim, we consider two variants of pure mobile ambients which differ in the way infinite processes can be defined; the former exploits process replication, while the latter is more general and permits recursive process definition. we analyse whether or not the elimination of ambient movement and/or name restriction reduces the expressive power of these two calculi, using the decidability of process termination as a yardstick. we prove that name restriction can be removed from both calculi without reducing the expressive power. on the other hand, the elimination of both ambient movement and name restriction strictly reduces the expressive power of both calculi. as far as the elimination of only ambient movement is concerned, we prove an interesting discrimination result: process termination is undecidable under recursive process definition, while it turns out to be decidable under process replication.
polynomial-size frege and resolution proofs of -connectivity and hex tautologies. a grid graph has rectangularly arranged vertices with edges permitted only between orthogonally adjacent vertices. the st- connectivity principle states that it is not possible to have a red path of edges and a green path of edges which connect diagonally opposite corners of the grid graph unless the paths cross somewhere.we prove that the propositional tautologies which encode the st-connectivity principle have polynomial-size frege proofs and polynomial-size tc0-frege proofs. for bounded-width grid graphs, the st-connectivity tautologies have polynomial-size resolution proofs. a key part of the proof is to show that the group with two generators, both of order two, has word problem in alternating logtime (alogtime) and even in tc0.conversely, we show that constant depth frege proofs of the st-connectivity tautologies require near-exponential size. the proof uses a reduction from the pigeonhole principle, via tautologies that express a "directed single source" principle sink, which is related to papadimitriou's search classes ppad and ppads (or, psk).the st-connectivity principle is related to urquhart's propositional hex tautologies, and we establish the same upper and lower bounds on proof complexity for the hex tautologies. in addition, the hex tautology is shown to be equivalent to the sink tautologies and to the one-to-one onto pigeonhole principle.
simplifying the weft hierarchy. we give simple, self-contained proofs of the basic hardness results for the classes w[t] of the weft hierarchy. we extend these proofs to higher levels of the hierarchy and illuminate the distinctions among its classes. the anti-monotone collapse at w[1, s] and the normalization of weft-t formulas arise as by-products of the proofs.
formal analysis of kerberos 5. we report on the detailed verification of a substantial portion of the kerberos 5 protocol specification. because it targeted a deployed protocol rather than an academic abstraction, this multiyear effort led to the development of new analysis methods in order to manage the inherent complexity. this enabled proving that kerberos supports the expected authentication and confidentiality properties, and that it is structurally sound; these results rely on a pair of intertwined inductions. our work also detected a number of innocuous but nonetheless unexpected behaviors, and it clearly described how vulnerable the cross-realm authentication support of kerberos is to the compromise of remote administrative domains.
new algorithms for exact satisfiability. the exact satisfiability problem is to determine if a cnf-formula has a truth assignment satisfying exactly one literal in each clause; exact 3-satisfiability is the version in which each clause contains at most three literals. in this paper, we present algorithms for exact satisfiability and exact 3-satisfiability running in time o(20.2325n) and o(20.1379n), respectively. the previously best algorithms have running times o(20.2441n) for exact satisfiability (methods oper. res. 43 (1981) 419-431) and o(20.1626n) for exact 3-satisfiability (annals of mathematics and artificial intelligence 43 (1) (2005) 173-193 and zapiski nauchnyh seminarov pomi 293 (2002) 118-128). we extend the case analyses of these papers and observe that a formula not satisfying any of our cases has a small number of variables, for which we can try all possible truth assignments and for each such assignment solve the remaining part of the formula in polynomial time.
extracting a data flow analyser in constructive logic. a constraint-based data flow analysis is formalised in the specification language of the coq proof assistant. this involves defining a dependent type of lattices together with a library of lattice functors for modular construction of complex abstract domains. constraints are represented in a way that allows for both efficient constraint resolution and correctness proof of the analysis with respect to an operational semantics. the proof of existence of a solution to the constraints is constructive which means that the extraction mechanism of coq provides a provably correct data flow analyser in ocaml from the proof. the library of lattices and the representation of constraints are defined in an analysis-independent fashion that provides a basis for a generic framework for proving and extracting static analysers in coq.
effective category and measure in abstract complexity theory. strong variants of the operator speed-up theorem, operator gap theorem and compression theorem are obtained using an effective version of baire category theorem. it is also shown that all complexity classes of recursive predicates have effective measure zero in the space of recursive predicates and, on the other hand, the class of predicates with almost everywhere complexity above an arbitrary recursive threshold has recursive measure one in the class of recursive predicates.
decidable containment of recursive queries. one of the most important reasoning tasks on queries is checking containment, i.e., verifying whether one query yields necessarily a subset of the result of another one. query containment is crucial in several contexts, such as query optimization, query reformulation, knowledge-base verification, information integration, integrity checking, and cooperative answering. containment is undecidable in general for datalog, the fundamental language for expressing recursive queries. on the other hand, it is known that containment between monadic datalog queries and between datalog queries and unions of conjunctive queries are decidable. it is also known that containment between unions of conjunctive two-way regular path queries, which are queries used in the context of semistructured data models containing a limited form of recursion in the form of transitive closure, is decidable. in this paper, we combine the automata-theoretic techniques at the base of these two decidability results to show that containment of datalog in union of conjunctive two-way regular path queries is decidable in 2exptime. by sharpening a known lower bound result for containment of datalog in union of conjunctive queries we show also a matching lower bound.
computation of arbitrage in frictional bond markets. in this paper we study the computational problem of arbitrage in a frictional market with a finite number of bonds and finite and discrete times to maturity. types of frictions under consideration include fixed and proportional transaction costs, bid-ask spreads, taxes, and upper bounds on the number of units for transaction. we develop a necessary and sufficient condition for the existence of arbitrage. in addition, we obtain some negative result on computational difficulty in general for arbitrage under those frictions: it is np-complete to identify whether there exists a cash-and-carry arbitrage transaction and it is np-hard to find an optimal cash-and-carry arbitrage transaction.
approximate sequencing for variable length tasks. based on applications to efficient information gathering over the web, czumaj et al. (algorithms and data structures (vancouver, bc, 1999), lecture notes in computer science, vol. 1663, springer, berlin, 1999, p. 297) studied the variable length sequencing problem (vlsp), showed it is np-complete, presented a polynomial time algorithm for a very restricted version and an approximation algorithm for a slightly less restricted version. in this paper, we pin-point the difficulty by showing that it is n-p-complete in a strong sense even to approximating the vlsp within a factor nk for any fixed integer k. in addition, we show it is np-hard to find the optimal solution even when all jobs follow the periodic property. motivated by the np-hardness of approximating vlsp, we consider an optimal version of maximizing the number of completed tasks and present an approximation algorithm with factor 2 and a polynomial time algorithm for optimal solution in the special case when the number of different types of tasks is restricted.
continuous-time computation with restricted integration capabilities. recursion theory on the reals, the analog counterpart of recursive function theory, is an approach to continuous-time computation inspired by the models of classical physics. in recursion theory on the reals, the discrete operations of standard recursion theory are replaced by operations on continuous functions such as composition and various forms of differential equations like indefinite integrals, linear differential equations and more general cauchy problems. we define classes of real recursive functions in a manner similar to the standard recursion theory and we study their complexity. we prove both upper and lower bounds for several classes of real recursive functions, which lie inside the elementary functions, and can be characterized in terms of space complexity. in particular, we show that hierarchies of real recursive classes closed under restricted integration operations are related to the exponential space hierarchy. the results in this paper, combined with earlier results, suggest that there is a close connection between analog complexity classes and subrecursive classes, at least in the region between flinspace and the primitive recursive functions.
the inapproximability of non-np-hard optimization problems. the inapproximability of non-np-hard optimization problems is investigated. techniques are given to show that the problems log dominating set and log hypergraph vertex cover cannot be approximated to a constant ratio in polynomial time unless the corresponding np-hard versions are also approximable in deterministic subexponential time. a direct connection is established between non-np-hard problems and a pcp characterization of np. reductions from the pcp characterization show that log clique is not approximable in polynomial time and max sparse sat does not have a fptas under the assumption that np ⊈ dtime(2o(√ n log n). a number of nontrivial approximation-preserving reductions are also presented, making it possible to extend inapproximability results to more natural non-np-hard problems such as tournament dominating set and rich hypergraph vertex cover.
incremental construction of minimal deterministic finite cover automata. we present a fast incremental algorithm for constructing minimal deterministic finite cover automata (dfca) for a given language. since it was shown that the minimal dfca for a language l has less states than the minimal deterministic finite automata (dfa) for the same language l, this technique seems to be the best choice for incrementally building the automaton for a large language, especially when the number of states in the dfca is significantly less than the number of states in the corresponding minimal dfa. we have implemented the proposed algorithm and have tested it against the best-known dfca minimization technique.
mergible states in large nfa. quite often, trivial problems stated for deterministic finite automata (dfa) are surprisingly difficult for the non-deterministic case (nfa). in any non-minimal dfa for a given regular language, we can find two equivalent states which can be "merged" without changing the accepted language. this is not the case for nfa, where we can have non-minimal automata with no "mergible" states. in this paper, we prove a very basic result for nfa, that for a given regular language, any nfa of size greater than a computable constant must contain mergible states. even more, we parameterized this constant in order to guarantee groups of an arbitrary number of mergible states.
a spatial logic for concurrency - ii. we present a modal logic for describing the spatial organization and the behavior of distributed systems. in addition to standard logical and temporal operators, our logic includes spatial operations corresponding to process composition and name hiding, and a fresh name quantifier. in part i of this work we study the fundamental semantic properties of our logic; the focus of the present part ii is on proof theory. the main contributions are a sequent-based proof system for our logic, and a proof of cut-elimination for its first-order fragment.
elimination of quantifiers and undecidability in spatial logics for concurrency. the introduction of spatial logics in concurrency is motivated by a shift of focus from concurrent systems towards distributed systems. aiming at a deeper understanding of the essence of dynamic spatial logics, we study a minimal spatial logic without quantifiers or any operators talking about names. the logic just includes the basic spatial operators void, composition and its adjunct, and the next step modality; for the model we consider a tiny fragment of ccs. we show that this core logic can already encode its own extension with quantification over actions, and modalities for actions. from this result, we derive several consequences. firstly, we establish the intensionality of the logic, we characterize the equivalence it induces on processes, and we derive characteristic formulas. secondly, we show that, unlike in static spatial logics, the composition adjunct adds to the expressiveness of the logic, so that adjunct elimination is not possible for dynamic spatial logics, even quantifier-free. finally, we prove that both model-checking and satisfiability problems are undecidable in our logic. we also conclude that our results extend to other calculi, namely the π-calculus and the ambient calculus.
integer partitions and the sperner property. the objectives of this paper are three-fold. first, we would like to call attention to a very attractive problem, the question of whether or not the poset of integer partitions ordered by refinement has the sperner property. we provide all necessary definitions, and enough bibliography to interest a newcomer in the problem. second, we prove four new theorems, two by exhaustive computation and two in the more traditional manner. finally, we highlight the central role played by larry harper in the literature of this subject.
new results on edge-bandwidth. the edge-bandwidth problem is an analog of the classical bandwidth problem, in which one has to label the edges of a graph by distinct integers such that the maximum difference of labels of any two incident edges is minimized. we prove tight bounds on the edge-bandwidth of hypercube and butterfly graphs, and complete k-ary trees which extends and improves on previous known results.