waashk/dblp huggingface dataset:
simple 8-state minimal time solution to the firing squad synchronization problem. the objective of the firing squad synchronization problem is to define sets of states and transition rules of a finite-state machine so that a one-dimensional array of such machines work synchronously. a minimal time solution to this problem was first found by goto in 1961. thereafter, other minimal time solutions were reported. i studied this problem and found an 8-state 119-rule solution by using a simple algorithm. the number of rules is much less than in baltzer's 8-state solution and the same as in mazoyer's 6-state solution.
temporal stratification tests for linear and branching-time deductive databases. we consider the problem of extending temporal deductive databases with stratified negation. we argue that the classical stratification test for deductive databases is too restrictive when one shifts attention to the temporal case. moreover, as we demonstrate, the (more general) local stratification approach is impractical: detecting whether a temporal deductive database is locally stratified is shown to be co-np hard (even if one restricts attention to programs that only use one predicate symbol and two constants). for these reasons we define temporal stratification, an intermediate notion between stratification and local stratification. we demonstrate that for the temporal deductive databases we consider, temporal stratification coincides with local stratification in certain important cases in which the latter is polynomial-time decidable. we then develop two algorithms for detecting temporal stratification. the first algorithm applies to linear-time temporal deductive databases and it is efficient and more general than existing approaches; however, the algorithm sacrifices completeness for efficiency since it does not cover the whole class of temporally stratified programs. the second algorithm applies to branching-time temporal deductive databases (which include as a special case the linear-time ones). this algorithm is more expensive from a computational point of view, but it covers the whole class of temporally stratified programs. we discuss the relative merits of the two algorithms and compare them with other existing approaches.
the complexity of equivalence and isomorphism of systems of equations over finite groups. we study the computational complexity of the isomorphism and equivalence problems on systems of equations over a fixed finite group. we show that the equivalence problem is in p if the group is abelian, and conp-complete if the group is non-abelian. we prove that if the group is non-abelian, then the problem of deciding whether two systems of equations over the group are isomorphic is conp-hard. if the group is abelian, then the isomorphism problem is graph isomorphism-hard. moreover, if we impose the restriction that all equations are of bounded length, then we prove that the isomorphism problem for systems of equations over finite abelian groups is graph isomorphism-complete. finally, we prove that the problem of counting the number of isomorphisms of systems of equations is no harder than deciding whether there exist any isomorphisms at all.
exact real number computations relative to hereditarily total functionals. we show that the continuous existential quantifier ∃ω is not definable in escardó's real-pcf from all functionals equivalent to a given total one in a uniform way. we further prove that relative to any total functional of type (i → i) → i which gives the maximum-value for any total input, we may, given a computable, total functional φ of type (r → r) → r find a real-pcf-definable total ψ equivalent to φ.
hierarchies of total functionals over the reals. we compare two natural constructions, the a-hierarchy and the r-hierarchy, of hereditarily total, continuous and extensional functionals of finite types over the reals. the a-hierarchy is based on the closed interval domain representation of the reals while the r-hierarchy is based on the binary negative digit representation. we show that the two hierarchies share a common maximal core. to this end, we construct an alternative to the r-hierarchy and prove a density theorem for this alternative hierarchy.
simple proof of the completeness theorem for second-order classical and intuitionistic logic by reduction to first-order mono-sorted logic. we present a simpler way than usual to deduce the completeness theorem for the second-order classical logic from the first-order one. we also extend our method to the case of second-order intuitionistic logic.
matrix algebra preconditioners for multilevel toeplitz systems do not insure optimal convergence rate. in the last decades several matrix algebra optimal and superlinear preconditioners (those assuring a strong clustering at the unity) have been proposed for the solution of polynomially ill-conditioned toeplitz linear systems. the corresponding generalizations for multilevel structures are neither optimal nor superlinear (see e.g. contemp. math. 281 (2001) 193). concerning the notion of superlinearity, it has been recently shown that the proper clustering cannot be obtained in general (see linear algebra appl. 343-344 (2002) 303; siam j. matrix anal. appl. 22(1) (1999) 431; math. comput. 72 (2003) 1305). in this paper, by exploiting a proof technique previously proposed by the authors (see contemp. math. 323 (2003) 313), we prove that the spectral equivalence and the essential spectral equivalence (up to a constant number of diverging eigenvalues) are impossible too. in conclusion, optimal matrix algebra preconditioners in the multilevel setting simply do not exist in general and therefore the search for optimal iterative solvers should be oriented to different directions with special attention to multilevel/multigrid techniques.
domain theory for concurrency. a simple domain theory for concurrency is presented. based on a categorical model of linear logic and associated comonads, it highlights the role of linearity in concurrent computation. two choices of comonad yield two expressive metalanguages for higher-order processes, both arising from canonical constructions in the model. their denotational semantics are fully abstract with respect to contextual equivalence. one language derives from an exponential of linear logic; it supports a straightforward operational semantics with simple proofs of soundness and adequacy. the other choice of comonad yields a model of affine-linear logic, and a process language with a tensor operation to be understood as a parallel composition of independent processes. the domain theory can be generalised to presheaf models, providing a more refined treatment of nondeterministic branching. the article concludes with a discussion of a broader programme of research, towards a fully fledged domain theory for concurrency.
using acceptors as transducers. we wish to use a given nondeterministic two-way multi-tape acceptor as a transducer by supplying the contents for only some of its input tapes, and asking it to generate the missing contents for the other tapes. we provide here an algorithm for assuring beforehand that this transduction always results in a finite set of answers. we also develop an algorithm for evaluating these answers whenever the previous algorithm indicated their finiteness. furthermore, our algorithms can be used for speeding up the simulation of these acceptors even when not used as transducers. copyright 2001 elsevier science b.v.
theoretical aspects of connectivity-based multi-hop positioning. we investigate the theoretical limits of positioning algorithms. in particular, we study scenarios where the nodes do not receive anchors directly (multi-hop) and where no physical distance or angle information whatsoever is available (connectivity-based). since we envision large-scale sensor networks as an application, we are interested in fast, distributed algorithms. as such, we show that plain hop algorithms are not competitive. instead, for one-dimensional unit disk graphs we present an optimal algorithm hs. for two or more dimensions, we propose an algorithm ghost which improves upon the basic hop algorithm in theory and in simulations.
algebraic and model-theoretic properties of tilings. we investigate the relations between the geometric properties of tilings and the algebraic and model-theoretic properties of associated relational structures. isomorphism and local isomorphism of tilings up to translation correspond to isomorphism and elementary equivalence of relational structures. in particular, two penrose tilings, or two robinson tilings, are elementarily equivalent. classical results concerning the local isomorphism property and the "extraction preorder" for tilings are generalized to uniformly locally finite relational structures.then, we define "equational structures", which generalize both cayley graphs of groups and relational structures associated to tilings, and for which we have an appropriate notion of free structure relative to a system of equations. for each finite system σ of prototiles and local configurations, we give a finite set of local conditions characterizing the connected relational structures which are homomorphic images of σ-tilings. it follows that tilings are free relative to finite systems of equations which express these conditions. we also prove that the theory of a tiling is superstable, model-complete, and can be axiomatized by ∀∃ sentences. one ∀∃ sentence suffices in the case of penrose tilings or robinson tilings.
integrating information visualization and retrieval for www information discovery. an important technology in knowledge discovery is to access the desired information from the large amount of data stored on the www. at present, such information can be accessed by a browser itself or by using a keyword search function. however, browsing is a time consuming task where a user must access individual pages one by one. furthermore, in keyword searches, it is difficult for users to provide reasonable keywords in knowledge discovery processes. this paper outlines an approach for integrating information visualization and retrieval into www information discovery. in this approach, the link structure of a web site is displayed in a 3-d hyperbolic tree in which the height of a node (corresponding to a web page) within the tree indicates a user's "interest" for each page. here, interest is calculated by a fitting function between a page and a user-supplied query (nested keywords). this measure can be used to filter uninteresting pages, reducing the size of the link structure. furthermore, each web page is modeled as semi-structured data and can also be displayed as a hyperbolic tree in which the result of query evaluation is visible. such functions are incorporated within our browser, allowing us to interactively discover desired pages from a large web site. we selected typical web sites to show the performance of the proposed method with improved accuracy and efficiency in www information discovery. here, accuracy indicates how surely the user accesses his/her desired documents, and efficiency indicates how quickly the user reaches the documents.
a uniform semantic proof for cut-elimination and completeness of various first and higher order logics. we present a natural generalization of girard's (first order) phase semantics of linear logic (theoret. comput. sci. 50 (1987)) to intuitionistic and higher-order phase semantics. then we show that this semantic framework allows us to derive a uniform semantic proof of the (first order and) higher order cut-elimination theorem (as well as a (first order and) higher order phase-semantic completeness theorem) for various different logical systems at the same time. our semantic proof works for various different logical systems uniformly in a strong sense (without any change of the argument of proof): it works for both first order and higher order versions and for linear, substructural, and standard logics uniformly, and for both their intuitionistic and classical versions uniformly.
effects of domain characteristics on instance-based learning algorithms. this paper presents average-case analyses of instance-based learning algorithms. the algorithms analyzed employ a variant of k-nearest neighbor classifier (k-nn). our analysis deals with a monotone m-of-n target concept with irrelevant attributes, and handles three types of noise: relevant attribute noise, irrelevant attribute noise, and class noise. we formally represent the expected classification accuracy of k-nn as a function of domain characteristics including the number of training instances, the number of relevant and irrelevant attributes, the threshold number in the target concept, the probability of each attribute, the noise rate for each type of noise, and k. we also explore the behavioral implications of the analyses by presenting the effects of domain characteristics on the expected accuracy of k-nn and on the optimal value of k for artificial domains.
a recognition and parsing algorithm for arbitrary conjunctive grammars. conjunctive grammars are basically context-free grammars with an explicit set intersection operation added to the formalism of rules. this paper presents a cubic-time recognition and parsing algorithm for this family of grammars, which is applicable to an arbitrary conjunctive grammar without any initial transformations.the algorithm is in fact an extension of the context-free recognition and parsing algorithm due to graham, harrison and ruzzo, and it retains the cubic time complexity of its prototype. it is shown that for the case of linear conjunctive grammars this algorithm can be modified to work in quadratic time and use linear space.the given algorithm is then applied to solve the membership problem for conjunctive grammars in polynomial time, and subsequently to prove the problem's p-completeness, as well as p-completeness of the membership problem for linear conjunctive grammars.
on the closure properties of linear conjunctive languages. linear conjunctive grammars are conjunctive grammars in which the body of each conjunct contains no more than a single nonterminal symbol. they can at the same time be thought of as a special case of conjunctive grammars and as a generalization of linear context-free grammars that provides an explicit intersection operation.although the set of languages generated by these grammars is known to include many important noncontext-free languages, linear conjunctive languages are still all square-time, and several practical algorithms have been devised to handle them, which makes this class of grammars quite suitable for use in applications.in this paper we investigate the closure properties of the language family generated by linear conjunctive grammars; the main result is its closure under complement, which implies that it is closed under all set-theoretic operations. we also consider several cases in which the concatenation of two linear conjunctive languages is certain to be linear conjunctive. in addition, it is demonstrated that linear conjunctive languages are closed under quotient with finite languages, not closed under quotient with regular languages, and not closed under ε-free homomorphism.
on the number of nonterminals in linear conjunctive grammars. the number of nonterminals in a linear conjunctive grammar is considered as a descriptional complexity measure of this family of languages. it is proved that a hierarchy collapses, and for every linear conjunctive grammar there exists and can be effectively constructed a linear conjunctive grammar that accepts the same language and contains exactly two nonterminals. this yields a partition of linear conjunctive languages into two nonempty disjoint classes of those with nonterminal complexity 1 and 2. the basic properties of the family of languages for which one nonterminal suffices are established. nonterminal complexity of grammars in the linear normal form is also investigated.
the dual of concatenation. a binary language-theoretic operation is proposed, which is dual to the concatenation of languages in the same sense as the universal quantifier in logic is dual to the existential quantifier; the dual of kleene star is defined accordingly. these operations arise whenever concatenation or star appear in the scope of negation. the basic properties of the new operations are determined in the paper. their use in regular expressions and in language equations is considered, and it is shown that they often eliminate the need of using negation, at the same time having an important technical advantage of being monotone. a generalization of context-free grammars featuring dual concatenation is introduced and proved to be equivalent to the recently studied boolean grammars.
unresolved systems of language equations: expressive power and decision problems. unresolved language equations and inequalities with various sets of operations are considered. it is proved that systems of unresolved equations with linear concatenation and union only, as well as systems with linear concatenation and intersection only, are as expressive as the more general unresolved inequalities with all boolean operations and unrestricted concatenation: the class of languages defined by unique (least, greatest) solutions of these systems is shown to coincide with the families of recursive (re, co-re, resp.) sets, which result extends even to individual equations of the form ∪ujxijvj = w∪∪yjxtjzj. on the other hand, unresolved equations with different sets of operations are shown to differ in the hardness of their decision problems, and it is demonstrated that several types of unresolved equations cannot effectively simulate each other in spite of the equality of the language families they define.
precedence-inclusion patterns and relational learning. in this paper we introduce precedence-inclusion patterns, which are sets with a strictly partially ordered set of strict partial orders, along with some additional structure. the definition of these structures reflects how multiple partial orders interact in a number of situations such as in text, images, and video. in particular, precedence-inclusion patterns generalize constituent structure trees familiar to computational linguists. our interest in these objects was initially sparked by their connection with problems of relational learning. we develop the general mathematical theory of precedence-inclusion patterns, we show that each finite set of finite precedence-inclusion relations has a minimal most specific generalization that is unique up to isomorphism, and we explain how this result relates to relational learning.
games characterizing levy-longo trees. we present a simple strongly universal innocent game model for levy-longo trees, i.e. every point in the model is the denotation of a unique levy-longo tree. the observational quotient of the model then gives a universal, and hence fully abstract, model of the pure lazy lambda calculus.
logical analysis of data with decomposable structures. in such areas as knowledge discovery, data mining and logical analysis of data, methodologies to find relations among attributes are considered important. in this paper, given a data set (t,f) where t ⊆ {0,1}n denotes a set of positive examples and f ⊆ {0,1}n denotes a set of negative examples, we propose a method to identify decomposable structures among the attributes of the data. we first study computational complexity of the problem of finding decomposable boolean extensions. since the problem turns out to be intractable (i.e., np-complete), we propose a heuristic algorithm in the second half of the paper. our method searches a decomposable partition of the set of all attributes by using the error sizes of almost-fit decomposable extensions as a guiding measure, and then finds structural relations among the attributes in the obtained partition. some results of numerical experiment on randomly generated data sets are also reported.
proof by computation in the coq system. in informal mathematics, statements involving computations are seldom proved. instead, it is assumed that readers of the proof can carry out the computations on their own. however, when using an automated proof development system based on type theory, the user is forced to find proofs for all claimed propositions, including computational statements. this paper presents a method to automatically prove statements from primitive recursive arithmetic. the method replaces logical formulas by boolean expressions. a correctness proof is constructed, which states that the original formula is derivable, if and only if the boolean expression equals true. because the boolean expression reduces to true, the conversion rule yields a trivial proof of the equality. by combining this proof with the correctness proof, we get a proof for the original statement.
optimal oblivious routing on d-dimensional meshes. in this work we consider deterministic oblivious k-k routing algorithms with buffer size o(k). we present an asymptotically optimal o(k√nd) step oblivious k-k routing algorithm for d-dimensional n × .... × n meshes of nd processors for all k ≥ 1 and d > 1. we further show how the algorithm can be used to achieve asymptotically optimal oblivious k-k routing algorithms on other networks.
avoiding coding tricks by hyperrobust learning. the present work introduces and justifies the notion of hyperrobust learning where one fixed learner has to learn all functions in a given class plus their images under primitive recursive operators. the following are shown: the notion of learnability does not change if the class of primitive recursive operators is replaced by a larger enumerable class of operators. a class is hyperrobustly ex-learnable iff it is a subclass of a recursively enumerable family of total functions. so, the notion of hyperrobust learning overcomes a problem of the traditional definitions of robustness which either do not preserve learning by enumeration or still permit topological coding tricks for the learning criterion ex. hyperrobust bc-learning as well as the hyperrobust version of ex-learning by teams are more powerful than hyperrobust ex-learning. the notion of bounded totalty reliable bc-learning is properly between hyperrobust ex-learning and hyperrobust bc-learning. furthermore, the bounded totally reliable bc-learnable classes are characterized in terms of infinite branches of certain enumerable families of bounded recursive trees. a class of infinite branches of another family of trees separates hyperrobust bc-learning from totally reliable bc-learning. furthermore, the notion of hyperrobust learning aided by selected context turns out to be much more restrictive than its counterpart for robust learning.
on the covering radius problem for ternary self-dual codes. in the present paper we develop a method to determine the cost weight distributions and covering radius of extremal ternary self-dual codes of various lengths. the notion of modified jacobi polynomials is introduced and elementary aspects of it art discussed. algebraic foundation has much room for further investigations. since the algorithms underlining in our approach to this problem are sound, and we can bet many numerical results as far as the computer runs in a reasonable time.
a coalgebraic view on positive modal logic. positive modal logic is the restriction of the modal local consequence relation defined by the class of all kripke models to the propositional negation-free modal language. the class of positive modal algebras is the one canonically associated with pml according to the theory of the algebrization of logics (lecture notes in logic, springer, berlin, 1996). a priestley-style duality is established between the category of positive modal algebras and the category of k+-spaces in (j. igpl 7 (6) (1999) 683). in this paper, we establish a categorical equivalence between the category k+ of k+-spaces and the category coalg(v) of coalgebras of a suitable endofunctor v on the category of priestley spaces.