waashk/dblp huggingface dataset:
commutation with codes. the centralizer of a set of words x is the largest set of words c(x)commuting with x: xc(x) = c(x)x. it has been a long standing open question due to [j.h. conway, regular algebra and finite machines, chapman & hall, london (1971).], whether the centralizer of any rational set is rational. while the answer turned out to be negative in general, see [m. kunc, proc. of icalp 2004, lecture notes in computer science, vol. 3142, springer, berlin, 2004, pp. 870-881.], we prove here that the situation is different for codes: the centralizer of any rational code is rational and if the code is finite, then the centralizer is finitely generated. this result has been previously proved only for binary and ternary sets of words in a series of papers by the authors and for prefix codes in an ingenious paper by [b. ratoandromanana, rairo inform. theor. 23(4) (1989) 425-444.]--many of the techniques we use in this paper follow her ideas. we also give in this paper an elementary proof for the prefix case.
multiple factorizations of words and defect effect. we prove that if x is a finite prefix set and w is a non-periodic bi-infinite word, possessing 3 disjoint x-factorizations, then the combinatorial rank of x is at most card(x)2. this is one of the rare cases when a cumulative defect effect is known to hold. finally, connections to the critical factorization theorem are discussed.
a defect theorem for bi-infinite words. we formulate and prove a defect theorem for bi-infinite words. let x be a finite set of words over a finite alphabet. if a nonperiodic bi-infinite word w has two x-factorizations, then the combinatorial rank of x is at most card(x)- 1, i.e., there exists a set f such that x ⊆ f+ with card(f) > card(x). moreover, in the case when the combinatorial rank of x equals card(x), the number of periodic bi-infinite words which have two different x-factorizations is finite.
conway's problem for three-word sets. we prove two results on commutation of languages. first, we show that the maximal language commuting with a three-element language, i.e. its centralizer, is rational, thus giving an affirmative answer to a special case of a problem proposed by conway in 1971. second, we characterize all languages commuting with a three-element code. the characterization is similar to the one proved by bergman for polynomials over noncommuting variables (see trans. am. math. soc. 137 (1969) 327 and algebraic combinatorics on words, cambridge university press, cambridge, 2000): a language commutes with a three-element code x if and only if it is a union of powers of x.
on the complexity of decidable cases of the commutation problem of languages. we investigate the complexity of basic decidable cases of the commutation problem for languages: testing the equality xy = yx for two languages x and y. we show that it varies from co-nexptime complete through pspace complete and co-np complete to deterministic polynomial time, when y is an explicitly given finite language and x is given by a cf grammar generating a finite language, a nondeterministic finite automaton (or a regular expression), an acyclic nondeterministic finite automaton or an explicitly given finite language, respectively. interestingly in most cases the complexity status does not change if instead of explicitly given finite y we consider general y of the same type as x. for deterministic finite automata the problem remains open, due to the asymmetry of the catenation.
generalized factorizations of words and their algorithmic properties. we formalize the notion of a factorization of a word, a so-called f-factorization, introduced in \cite{kmp} when solving some open problems on word equations. we show that most of the factorizations considered in the literature fit well into that framework, and in particular that central algorithmic problems, such as the uniqueness or the synchronizability, remain polynomial time solvable for an important and large class of f-factorizations, namely for regular f-factorizations.
synchronizing finite automata on eulerian digraphs. cerný's conjecture and the road coloring problem are two open problems concerning synchronization of finite automata. we prove these conjectures in the special case that the vertices have uniform in- and outdegrees.
theory of cellular automata: a survey. this article surveys some theoretical aspects of cellular automata ca research. in particular, we discuss classical and new results on reversibility, conservation laws, limit sets, decidability questions, universality and topological dynamics of ca. the selection of topics is by no means comprehensive and reflects the research interests of the author. the main goal is to provide a tutorial of ca theory to researchers in other branches of natural computing, to give a compact collection of known results with references to their proofs, and to suggest some open problems.
on properties of bond-free dna languages. the input data for dna computing must be encoded into the form of single or double dna strands. as complementary parts of single strands can bind together forming a double-stranded dna sequence, one has to impose restrictions on these sets of dna words (languages) to prevent them from interacting in undesirable ways. we recall a list of known properties of dna languages which are free of certain types of undesirable bonds. then we introduce a general framework in which we can characterize each of these properties by a solution of a uniform formal language inequation. this characterization allows us among others to construct (i) a uniform algorithm deciding in polynomial time whether a given dna language possesses any of the studied properties, and (ii) in many cases also an algorithm deciding whether a given dna language is maximal with respect to the desired property.
aspects of shuffle and deletion on trajectories. word and language operations on trajectories provide a general framework for the study of properties of sequential insertion and deletion operations. a trajectory gives a syntactical constraint on the scattered insertion (deletion) of a word into(from) another one, with an intuitive geometrical interpretation. moreover, deletion on trajectories is an inverse of the shuffle on trajectories. these operations are a natural generalization of many binary word operations like catenation, quotient, insertion, deletion, shuffle, etc. besides they were shown to be useful, e.g. in concurrent processes modelling and recently in biocomputing area.we begin with the study of algebraic properties of the deletion on trajectories. then we focus on three standard decision problems concerning linear language equations with one variable, involving the above mentioned operations. we generalize previous results and obtain a sequence of new ones. particularly, we characterize the class of binary word operations for which the validity of such a language equation is (un)decidable, for regular and context-free operands.
continuous monoids and semirings. different kinds of monoids and semirings have been defined in the literature, all of them named "continuous". we show their relations. the main technical tools are suitable topologies, among others a variant of the well-known scott topology for complete partial orders.
generalized and geometric ramsey numbers for cycles. let cn denote the cycle of length n. the generalized ramsey number of the pair (cn , ck) denoted by; r(cn, ck)is the smallest positive integer rsuch that any complete graph with r vertices whose edges are coloured with two di/erent colours contains either a monochromatic cycle of length n in the 1rst colour or a monochromatic cycle of length k in the second colour. generalized ramsey numbers for cycles were completely determined by faudree-schelp and rosta, based on earlier works of bondy, erd&ohuml;s and gallai. unfortunately, both proofs are quite involved and di9cult to follow. in the present paper we treat this problem in a uni1ed, self-contained and simpli1ed way. we also extend this study to a related geometric problem, where we colour the straight-line segments determined by a 1nite number of points in the plane. in this case, the monochromatic subgraphs are required to satisfy an additional (non-crossing) geometric condition.
correctness of constructing optimal alphabetic trees revisited. several new observations which lead to new correctness proofs of two known algorithms (hu-tucker and garsia-wachs) for construction of optimal alphabetic trees are presented. a generalized version of the garsia-wachs algorithm is given. proof of this generalized version works in a structured and illustrative way and clarifies the usually poorly-understood behavior of both the hu-tucker and garsia-wachs algorithms. the generalized version permits any non-negative weights, as opposed to strictly positive weights required in the original garsia-wachs algorithm. new local structural properties of optimal alphabetic trees are given. the concept of {\em well-shaped segment\/} (a part of an optimal tree) is introduced. it is shown that some parts of the optimal tree are known in advance to be well-shaped, and this implies correctness of the algorithms rather easily. the crucial part of the correctness proof of the garsia-wachs algorithm, namely the {\em structural theorem}, is identified. the correctness proof of the hu-tucker algorithm consists of showing a very simple mutual simulation between this algorithm and the garsia-wachs algorithm. for this proof, it is essential to use the generalized version of garsia-wachs algorithm, in which an arbitrary locally minimal pair is processed, not necessarily the rightmost minimal pair. such a generalized version is also needed for parallel implementations. another result presented in this paper is the clarification of the problem of resolving ties (equalities between weights of items) in the hu-tucker algorithm. this is related to the proof, by simulation, of correctness of the hu-tucker algorithm. it is shown that the condition that there are no ties may generally be assumed without harm and that, essentially, the hu-tucker algorithm avoids ties automatically.
zero testing of p-adic and modular polynomials. we obtain new algorithms to test if a given multivariate polynomial over p-adic fields is identical to zero. we also consider zero testing of polynomials in residue rings. the results complement a series of known results about zero testing of polynomials over integers, rationals and finite fields.
alphabet-independent optimal parallel search for three-dimensional patterns. we give an alphabet-independent optimal parallel algorithm for the searching phase of three-dimensional pattern-matching. all occurrences of a three dimensional pattern p of shape $m \times m \times m$ in a text t of shape $n \times n \times n$ are to be found. our algorithm works in $\log m$ time with ${\mathcal o}(n/\log(m))$ processors of a {\em crew pram}, where $n = n^3$. the ideas from \cite{abf93} are used. surprisingly, the extension of the two dimensional matching to the three dimensional one is not a trivial modification. the searching phase in three dimensions explores classification of two-dimensional periodicities of the cubic pattern. some projection techniques are developed to deal with three dimensions. the periodicites of the patern with respect to its faces are investigated. the nonperiodicities imply some sparseness properties, while periodicities imply other special useful properties ({\ie} monotonicity) of the set of occurrences. both types of properties are useful in deriving an efficient algorithm.
an approximability result of the multi-vehicle scheduling problem on a path with release and handling times. in this paper, we consider a scheduling problem of vehicles on a path g with n vertices and n - 1 edges. there are m identical vehicles. each vertex in g has exactly one job. any of the n jobs must be processed by some vehicle. each job has a release time and a handling time. with the edges, symmetric travel times are associated. the problem asks to find an optimal schedule of the m vehicles that minimizes the maximum completion time of all the jobs. the problem is known to be np-hard for any fixed m ≥ 2. in this paper, we show that the problem with a fixed m admits a polynomial time approximation scheme. our algorithm can be extended to the case where g is a tree so that a polynomial time approximation scheme is obtained if m and the number of leaves in g are fixed.
enhancements of partitioning techniques for image compression using weighted finite automata. weighted finite automata are efficient structures for the storage of digital images. the choice of the image partitioning technique is important to achieve good compression results. in this paper we examine two promising techniques by measuring the compression performance at well-known test images.
undecidable properties of monoids with word problem solvable in linear time. let c1 be the class of finitely presented monoids with word problem solvable in linear time. let p be a markov property of monoids related to class c1 in some sense. it is undecidable given a monoid in c1 whether it satisfies p. let c and c' be classes of finitely presented monoids with word problem solvable in some time-bounds. if c contains c1 and c' properly contains c, then it is undecidable given a monoid in c' whether it belongs to c.
undecidable properties of monoids with word problem solvable in linear time. part ii-- cross sections and homological and homotopical finiteness conditions. using a particular simulation of single-tape turing machines by finite string-rewriting systems the first two authors have shown that all linear markov properties are undecidable for the class of finitely presented monoids with linear-time decidable word problem. expanding on this construction it is shown here that also many properties that are not known to be linear markov properties are undecidable for this class of monoids. these properties include the existence of context-free or regular cross-sections, the existence of finite convergent presentations, the property of being automatic, and the homological and homotopical finiteness properties left- and right-fpn (n ≥ 3), fht, and fdt.
universal test for quantum one-way permutations. the next bit test was introduced by blum and micali and proved by yao to be a universal test for cryptographic pseudorandom generators. on the other hand, no universal test for the cryptographic one-wayness of functions (or permutations) is known, although the existence of cryptographic pseudorandom generators is equivalent to that of cryptographic one-way functions. in the quantum computation model, kashefi, nishimura and vedral gave a sufficient condition of (cryptographic) quantum one-way permutations and conjectured that the condition would be necessary. in this paper, we affirmatively settle their conjecture and complete a necessary and sufficient condition for quantum one-way permutations. the necessary and sufficient condition can be regarded as a universal test for quantum one-way permutations, since the condition is described as a collection of stepwise tests similar to the next bit test for pseudorandom generators.
a unified language processing methodology. this paper discusses a mathematical concept of language that models both artificial and natural languages and thus provides a framework for a unified language processing methodology. this concept of a language is regarded as a communication tool that allows language users to develop knowledges, while interacting with their universe of discourse, and to communicate with each other, while exchanging knowledges. criteria for consistent usage of a language are established using a galois connection between language syntax and language semantics. solutions to ambiguity, paraphrase, attitude, and other problems concerning the relationship between syntax and semantics are addressed. a general schema for language specification is introduced and algorithms that perform language generation and language analysis are discussed as universal tools defined by the specification schema. language transformations performed by various kinds of translators are examined and correctness criteria of these translators are defined using the language galois connection. the paper is structured as follows: section1 introduces the framework and justifies the necessity of a unified methodology for language processing. section2 presents the mathematical concept of a language. section3 illustrates the mathematical concept of a language with three kinds of language structures: natural language, logical language, and programming language. section4 discusses the algebraic mechanism of language specification that unifies the methodology for language processing tool development. section5 formalizes the criterion for the consistency of the language usage, defines the architecture of a unified language processing system, and shows how the consistency criteria for language usage can be employed as correctness criteria for the algorithms performing various language transformations.
on congruences of automata defined by directed graphs. we consider automata defined by graph algebras of directed graphs, characterize all congruences on these automata, and give a complete description of all automata of this type satisfying three properties for congruences introduced and considered in the literature by analogy with classical semisimplicity conditions that play important roles in structure theory.
clustering for petri nets. this work builds a bridge from • clustering techniques--merging neighbouring nodes which is a key feature for software engineering and the practical applications of petri nets--to • folding techniques--merging only transitions with transitions and places with places, preserving behaviour and allowing theoretical connections to many models of concurrency.a new category of petri nets is introduced. morphisms support clustering, offering attractive properties to software engineering and integrating smoothly with invariants. a computationally reasonable adjunction connects it to folding-based petri nets, namely, to two new cocomplete and complete categories. the dichotomy of structure and behaviour of petri nets is expressed as compatible adjunctions to behavioural categories. finally reachability and process semantics are attached categorically and a new variant of occurrence nets is proposed as a purer image of causality and branching. this framework offers categorical support for practical applications of petri nets.
uncomputability: the problem of induction internalized. i argue that uncomputable formal problems are intuitively, mathematically, and methodologically analogous to empirical problems in which hume's problem of induction arises. in particular, i show that a version of ockham's razor (a preference for simple answers) is advantageous in both domains when infallible inference is infeasible. a familiar response to the empirical problem of induction is to conceive of empirical inquiry as an unending process that converges to the truth without halting or announcing for sure when the truth has been reached. on the strength of the analogies developed, i recommend the adoption of a similar perspective on uncomputable formal problems. one obtains, thereby, a well-defined notion of "hyper-computability" based entirely on classical computational models and on standards of success that have long been regarded as natural in the empirical domain.
infinitary lambda calculus. in a previous paper we have established the theory of transfinite reduction for orthogonal term rewriting systems. in this paper we perform the same task for the lambda calculus. from the viewpoint of infinitary rewriting, the böhm model of the lambda calculus can be seen as an infinitary term model. in contrast to term rewriting, there are several different possible notions of infinite term, which give rise to different böhm-like models, which embody different notions of lazy or eager computation.
securing the .net programming model. the security of the .net programming model is studied from the standpoint of fully abstract compilation of c#. a number of failures of full abstraction are identified, and fixes described. the most serious problems have recently been fixed for version 2.0 of the .net common language runtime.
closure properties of linear context-free tree languages with an application to optimality theory. context-free tree grammars, originally introduced by rounds [math. systems theory 4(3) (1970) 257-287], are powerful grammar devices for the definition of tree languages. the properties of the class of context-free tree languages have been studied for more than three decades now. particularly important here is the work by engelfriet and schmidt [j. comput. system sci. 15(3) (1977) 328-353, 16(1) (1978) 67-99]. in the present paper, we consider a subclass of the class of context-free tree languages, namely the class of linear context-free tree languages. a context-free tree grammar is linear, if no rule permits the copying of subtrees. for this class of linear context-free tree languages we show that the grammar derivation mode, which is very important for the general class of context-free tree languages, is immaterial. the main result we present is the closure of the class of linear context-free tree languages under linear frontier-to-root tree transduction mappings. two further results are the closure of this class under linear root-to-frontier tree transduction mappings and under intersection with regular tree languages.the results of the first part of the paper are applied to the formalisation of optimality theory. optimality theory (ot), introduced by prince and smolensky [tech. report 1993], is a linguistic framework in which the mapping of one level of linguistic representation to another is based on rules and filters. the rules generate candidate expressions in the target representation, which are subsequently checked against the filters, so that only those candidates remain that survive this filtering process. a proposal to formalise the description of ot using formal language theory and in particular automata theory was presented by karttunen [proceedings of international workshop on finite-state methods in natural language processing, 1998, pp. 1-12] and frank and satta [comput. linguistics 24 (1998) 307-315]. the main result of these papers is that if the generator is defined as a finite-state string transducer and the filters are defined by finite-state string automata, then the whole ot-system can be defined by means of a finite-state string transducer. considering the fact that most parts of linguistics have trees as their underlying data structures instead of strings, we show here that generators can be extended to linear frontier-to-root tree transducers on linear context-free tree languages--with constraints being regular tree languages--while the computation of optimal candidates can still be performed using finite-state techniques (over trees).