waashk/dblp huggingface dataset:
discovering instances of poetic allusion from anthologies of classical japanese poems. waka is a form of traditional japanese poetry with a 1300-year history. in this paper, we attempt to semi-automatically discover instances of poetic allusion, or more generally, to find similar poems in anthologies of waka poems. one reasonable approach would be to arrange all possible pairs of poems in two anthologies in decreasing order of similarity values, and to scrutinize high-ranked pairs by human effort. the means of defining similarity between waka poems plays a key role in this approach. in this paper, we generalize existing (dis)similarity measures into a uniform framework, called string resemblance systems, and using this framework, we develop new similarity measures suitable for finding similar poems. using the measures, we report successful results in finding instances of poetic allusion between two anthologies kokin-shu and shin-kokin-shu. most interestingly, we have found an instance of poetic allusion that has never before been pointed out in the long history of waka research.
discovering characteristic expressions in literary works. we attempt to extract characteristic expressions from literary works. that is, given two collections of literary works, one of which is written by a particular author (positive examples) and the other by a different author (negative examples), the problem is to find expressions that appear frequently in the positive examples but which are seldom found in the negative examples. this is considered as a special case of the optimal pattern discovery from textual data, in which only the substring patterns are considered. one approach would be to create a list of text substrings sorted according to goodness, and to scrutinize the first part of the list by human efforts. since there is no word boundary in japanese texts, a substring is often a fragment of a word or phrase. a method to assist domain experts who are involved in this task is a key problem. in this paper, we propose partitioning the text substrings into equivalence classes under an equivalence relation on strings, originally defined by blumer et al. (j. acm 34(3) (1987) 578). the equivalence relation has the desirable property that all members of each equivalence class necessarily have a unique goodness value. this idea effectively reduces the inefficiency of the task of evaluating mined patterns. we also present a method for browsing possible superstrings of a focused string as well as its context. we report successful results with two pairs of anthologies of classical japanese poems. we expect that the extracted expressions may lead to discovering overlooked aspects of individual poets.
top-down decision tree learning as information based boosting. we consider a boosting technique that can be directly applied to multiclass classification problems. although many boosting algorithms have been proposed so far, most of them are developed essentially for binary classification problems, and in order to handle multiclass classification problems, they need to be reduced somehow to binary ones. in order to avoid such reductions, we introduce a notion of the pseudo-entropy function g that gives an information-theoretic criterion, called the conditional g-entropy, for measuring the loss of hypotheses. the conditional g-entropy turns out to be useful for defining the weakness of hypotheses that approximate, in some way, a multiclass function in general, so that we can consider the boosting problem without reduction. we show that the top-down decision tree learning algorithm using the conditional g-entropy as its splitting criterion is an efficient boosting algorithm. namely, the algorithm intends to minimize the conditional g-entropy, rather than the classification error. in the binary case, our algorithm turns out to be identical to the error-based boosting algorithm proposed by kearns and mansour, and our analysis gives a simpler proof of their results.
predicting nearly as well as the best pruning of a decision tree through dynamic programming scheme. helmbold and schapire gave an on-line prediction algorithm that, when given an unpruned decision tree, produces predictions not much worse than the predictions made by the best pruning of the given decision tree. in this paper, we give two new on-line algorithms. the first algorithm is based on the observation that finding the best pruning can be efficiently solved by a dynamic programming in the "batch" setting where all the data to be predicted are given in advance. this algorithm works well for a wide class of loss functions, whereas the one given by helmbold and schapire is only described for the absolute loss function. moreover, the algorithm given in this paper is so simple and general that it could be applied to many other on-line optimization problems solved by dynamic programming. we also explore the second algorithm that is competitive not only with the best pruning but also with the best prediction values which are associated with nodes in the decision tree. in this setting, a greatly simplified algorithm is given for the absolute loss function. it can be easily generalized to the case where, instead of using decision trees, data are classified in some arbitrarily fixed manner.
rigorous results for mean field models for spin glasses. in this paper i explain why i believe that it is important to prove rigorous results about mean field models for spin glasses, and why i think it is difficult. i also describe at a high level what mathematicians have been able to prove.
actor theories in rewriting logic. the actor theory framework is a general semantic framework, based on the actor computation model, for specifying and reasoning about components of open distributed systems. it can be used to define both operational and trace-like interaction semantics for actor programming languages and specification notations. it can also be used to directly specify actor system components. the framework allows descriptions of system components written using different notations or at different levels of abstraction to be related: translations between actor programming languages can be shown to preserve interaction semantics, notions of satisfaction and refinement for specification notations can be defined and, using actor theory transformations, different descriptions of a component can be shown to be equivalent. in this paper we define the notion of an equationally presented actor theory and a mapping of equational presentations to theories in rewriting logic. we show that this mapping gives a correct representation of actor theory semantics by defining a correspondence between finite actor theory computations and rewrite theory proofs. to treat infinite computations and admissibility we extend the rewriting logic initial model construction to include infinite proofs, extend the mapping to infinite computations, and show that the correspondence preserves interaction semantics.
on size reduction techniques for multitape automata. we present a method for size reduction of two-way multitape automata. our algorithm applies local transformations that change the order in which transitions concerning different tapes occur in the automaton graph, and merge suitable states into a single state. our work is motivated by implementation of a language for string manipulation in database systems where string predicates are compiled into two-way multitape automata. additionally, we present a (one-tape) nfa reduction algorithm that is based on a method proposed for dfa minimization by kameda and weiner, and apply this algorithm, combined with the multitape automata reduction algorithm, on our multitape automata. empirical results on the performance of our method when applied on some multitape automata originating from string predicates are reported.
bideterministic automata and minimal representations of regular languages. bideterministic automata are deterministic automata with the property of their reversal automata also being deterministic. it has been known that a bideterministic automaton is the minimal deterministic automaton accepting its language. this paper shows that any bideterministic automaton is the unique minimal automaton among all (including nondeterministic) automata accepting the same language. we also present a more general result that shows that under certain conditions a minimal deterministic automaton accepting some language or the reversal of the minimal deterministic automaton of the reversal language is a minimal automaton representation of the language. these conditions can be checked in polynomial time.
on syntactic monoids of biunitary submonoids determined by homomorphisms from free semigroups onto completely simple semigroups. we deal with the maximal bifix code construction which is a natural generalization of a group code construction. for a surjective morphism ϕ from a free monoid a* onto a completely simple semigroup with an adjoined identity m (g; i, j; σ)1 and a submonoid s of m(g; i, j; σ)1, under certain conditions, the base of a submonoid ϕ-1 (s) is a maximal bifix code x. we investigate the relationships between the surjective morphism ϕ and the syntactic monoid of the monoid generated by x.
query complexity of membership comparable sets. this paper investigates how many queries to k-membership comparable sets are needed in order to decide all (k + 1)-membership comparable sets. for k ≥ 2 this query complexity is at least linear and at most cubic. as a corollary, we obtain that more languages are o(log n)-membership comparable than truth-table reducible to p-selective sets.
emerging behavior as binary search trees are symmetrically updated. when repeated updates are made to a binary search tree, the expected search cost tends to improve, as observed by knott. for the case in which the updates use an asymmetric deletion algorithm, the knott effect is swamped by the behavior discovered by eppinger. the knott effect applies also to updates using symmetric deletion algorithms, and it remains unexplained, along with several other trends in the tree distribution. it is believed that updates using symmetric deletion do not cause search cost to deteriorate, but the evidence is all experimental. the contribution of this paper is to model separately several different trends which may contribute to or detract from the knott effect, including a previously unreported centripetal tendency.
detecting quantum entanglement. we review the criteria for separability and quantum entanglement, both in a bipartite as well as a multipartite setting. we discuss bell inequalities, entanglement witnesses, entropic inequalities, bound entanglement and several features of multipartite entanglement. we indicate how these criteria bear on the experimental detection of quantum entanglement.
characterization of real time iterative array by alternating device. in this paper, we show that real time k-dimensional iterative arrays are equivalent through reverse to real time one-way alternating k-counter automata.
two-dimensional cellular automata and deterministic on-line tessalation automata. in this work we consider the relationships between the classes of two-dimensional languages defined by deterministic on-line tessellation automata and by real time two-dimensional cellular automata with moore and von neumann neighborhood. we generalize the result known for one-dimensional cellular automata to two-dimensional cellular automata with von neumann neighborhood: the class of real time cellular automata is closed under rotation of 180° if and only if real time cellular automata is equivalent to linear time cellular automata.
two-dimensional cellular automata and their neighborhoods. we investigate how the choice of the neighborhood can influence the computation ability of two-dimensional cellular automata. we present also a strict inclusion between low and high complexity classes of two-dimensional cellular automata.
closure properties of cellular automata. concerning the power of one-dimensional cellular automata recognizers, ibarra and jiang have proved that real time cellular automata (ca) and linear time ca are equivalent if and only if real time ca is closed under reverse. in this paper we investigate the question of equality of real time ca and linear time ca with respect to the operations of concatenation and cycle. in particular, we prove that if real time ca is closed under concatenation then real time ca is as powerful as linear time ca on the unary languages. we also prove that the question of knowing whether real time ca is as powerful than linear time ca is equivalent to the question of whether real time ca is closed under cycle. moreover, in the case of two-dimensional ca recognizers, we investigate how restricted communication reduces the computational power. in particular, we show that real time ca and linear time ca with restricted variants of moore and von neumann neighborhoods are not closed under rotation. furthermore, they are not equivalent to real time ca with moore or von neumann neighborhoods.
complete symbolic reachability analysis using back-and-forth narrowing. we propose a method called back-and-forth narrowing for solving reachability goals of the form (∃x→).t1 → *t'1...∧tn→*t'n in general term rewrite systems. the method is a complete semi-decision procedure in the sense that it is guaranteed to find a solution when one exists, but in general it may not terminate when there are no solutions. the completeness result is very general in that it makes no assumptions about the given term rewrite system. specifically, the rewrite rules need not be linear, confluent, or terminating, and can even have extra-variables in the right-hand side. such generality is often essential while modeling concurrent systems or axiomatizing inference systems as rewrite rules, and in such applications back-and-forth narrowing can be used as a sound and complete technique for symbolic reachability analysis or as a deductive procedure for proving existential formulae.
an o(n log n)-algorithm for finding a domino tiling of a plane picture whose number of holes is bounded. we consider the problem of tiling a plane picture with dominoes, this picture can be with holes or without holes. we give a necessary and sufficient condition for the existence of such a tiling and then we deduce an algorithm to decide whether a picture is tileable or not and if it is, to determine a tiling. this algorithm runs in o(kn + n log n) time, where n and k are the respective numbers of cells and holes. we also propose a simplified version of this algorithm which is linear in the area enclosed by the outer boundary, provided the picture has a bounded number of holes.
on the approximability of the steiner tree problem. we show that it is not possible to approximate the minimum steiner tree problem within 1+1/162 unless rp=np. the currently best known lower bound is 1 +1/400. the reduction is from hastad's nonapproximability result for maximum satisfiability of linear equation modulo 2. the improvement on the nonapproximability ratio is mainly based on the fact that our reduction does not use variable gadgets, this idea was introduced by papadimitriou and vempala.
uniform and nonuniform recognizability. deterministic and nondeterministic finite-state recognizability over finite structures are introduced in an algebraic setting, avoiding detailed computational conventions as needed in the definition of finite-state acceptors. for deterministic recognizability, the classical approach is adopted, using a "uniform" homomorphism from the input domain (consisting of terms) into a finite algebra. for the nondeterministic case, we refer to relational input structures and to an acceptance via relational homomorphisms (which are applied "nonuniformly" since they depend on the input structures). we show how this approach encompasses known models of nondeterministic automata over finite words, trees, pictures, and graphs, and present some elementary metaresults connecting uniform recognizability, nonuniform recognizability, and monadic second-order logic.
rauzy substitutions and multi-dimensional sturmian words. recently, berthé and the author developed a method to construct a multi-dimensional sturmian word as a limit of a sequence of words on lattice domains. in the present paper, the reach of the approach is studied in the special case of rauzy substitutions.
unions of non-disjoint theories and combinations of satisfiability procedures. in this paper we outline a theoretical framework for the combination of decision procedures for constraint satisfiability. we describe a general combination method which, given a procedure that decides constraint satisfiability with respect to a constraint theory t1 and one that decides constraint satisfiability with respect to a constraint theory t2, produces a procedure that (semi-)decides constraint satisfiability with respect to the union of t1 and t2. we provide a number of model-theoretic conditions on the constraint language and the component constraint theories for the method to be sound and complete, with special emphasis on the case in which the signatures of the component theories are non-disjoint. we also describe some general classes of theories to which our combination results apply, and relate our approach to some of the existing combination methods in the field.
petri net reactive modules. in this paper we model (discrete) reactive systems that may interact with each other by petri net reactive modules (modules, for short) which are classical petri nets together with a distinguished subset of interface places. we consider then an asynchronous composition operation of modules and, closely related to it, a decomposition operation. we show that any process (concurrent execution) of a composition of two modules can be decomposed into processes of "shifted" components for which a p-composition function exists, and vice versa. based on this result, a compositional semantics of modules is then defined. applications of process decomposition to replacement techniques of petri nets and in proving correctness of petri net structural transformations, are further discussed.
some relationships between logics of programs and complexity theory. the aim of this paper is to show that some open problems in comparative schematology and in logics of programs are equivalent to open problems in complexity theory. in particular we show that pspace = ptime holds if and only if flow-diagrams with arrays are of the same computational power as recursive procedures. these statements are also equivalent to the following statement: logics based on the above-mentioned classes of program schemes have equal expressive power. a similar characterization may be given for other complexity classes.
how to turn a second-order cellular automaton into a lattice gas: a new inversion scheme. in second-order cellular automata, the signals made available to the local transition function include, besides the current state of a site's neighbors, also the previous state of the site itself. some similarities had been noted, especially in physics simulations, between certain second-order cellular automata and certain lattice gases.here we show how to construct, for any second-order cellular automaton, a lattice gas having isomorphic functional behavior. (paradoxically, this isomorphism of function is achieved by compromising on the isomorphism of structure: namely, the group of translation symmetries of the resulting lattice gas is coarser than that of the original cellular automaton.) the advantage of our construction is that, while invertibility in cellular automata is not directly deducible from the local map (indeed, it is in general undecidable), in the second-order case the invertibility of the cellular automaton goes hand-in-hand with that of the corresponding lattice gas--and for lattices gases invertibility is trivially decidable on the basis of the local structure.from a physical viewpoint, our construction illustrates a trade-off between two ways of achieving a "force" of a given range. in a cellular automaton, multiple copies of a signal are made and distributed in parallel to several sites, explicitly providing the desired fanout width. in a lattice gas, with our construction, one can let a single signal serially service a number of sites along an appropriate spacetime route. the latter method is better suited to a nondissipative implementation of the dynamics.
on reasoning about structural equality in xml: a description logic approach. we define a boolean complete dialect of description logic called dlfdreg that can be used to reason about structural equality in semistructured ordered data in the presence of document type definitions. this application depends on the novel ability of dlfdreg to express functional dependencies over possibly infinite sets of feature paths defined by regular languages. we also present a decision procedure for the associated logical implication problem. the procedure underlies a mapping of such problems to satisfiability problems of datalog¬ns.
on the number of occurrences of all short factors in almost all words. we previously proved that almost all words of length n over a finite alphabet a with m letters contain as factors all words of length k(n) over a as n → ∞, provided lim supn → ∞k(n)/logn<1/ logm.in this note it is shown that if this condition holds, then the number of occurrences of any word of length k(n) as a factor into almost all words of length n is at least s(n), where limn → ∞log s(n)/log(n)=0, in particular, this number of occurrences is bounded below by c log n as n → ∞, for any absolute constant c > 0.
a characterization of the words occurring as factors in a minimum number of words. we show by an injective proof that a word w of length k≥2 occurs as a factor in a minimum number of length n (n > k) if and only if all letters of w are equal.
the worst-case time complexity for generating all maximal cliques and computational experiments. we present a depth-first search algorithm for generating all maximal cliques of an undirected graph, in which pruning methods are employed as in the bron-kerbosch algorithm. all the maximal cliques generated are output in a tree-like form. subsequently, we prove that its worst-case time complexity is o(3n/3) for an n-vertex graph. this is optimal as a function of n, since there exist up to 3n/3 maximal cliques in an n-vertex graph. the algorithm is also demonstrated to run very fast in practice by computational experiments.
channel graphs of bit permutation networks. channel graphs have been widely used in the study of blocking networks. in this paper, we show that a bit permutation network has a unique channel graph if and only if it is connected, and two connected bit permutation networks are isomorphic if and only if their channel graphs are isomorphic.