Processing math: 100%
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at customercare@wspc.com for any enquiries.

SEARCH GUIDE  Download Search Tip PDF File

  • articleNo Access

    ON CONTEXT-FREE LANGUAGES OF SCATTERED WORDS

    It is known that if a Büchi context-free language (BCFL) consists of scattered words, then there is an integer n, depending only on the language, such that the Hausdorff rank of each word in the language is bounded by n. Every BCFL is a Muller context-free language (MCFL). In the first part of the paper, we prove that an MCFL of scattered words is a BCFL iff the rank of every word in the language is bounded by an integer depending only on the language.

    Then we establish operational characterizations of the BCFLs of well-ordered and scattered words. We prove that a language is a BCFL consisting of well-ordered words iff it can be generated from the singleton languages containing the letters of the alphabet by substitution into ordinary context-free languages and the ⍵-power operation. We also establish a corresponding result for BCFLs of scattered words and define expressions denoting BCFLs of well-ordered and scattered words. In the final part of the paper we give some applications.

  • articleNo Access

    OPERATIONAL CHARACTERIZATION OF SCATTERED MCFLs

    We give a Kleene-type operational characterization of Muller context-free languages (MCFLs) of well-ordered and scattered words.

  • articleNo Access

    Abelian Complexity and Frequencies of Letters in Infinite Words

    Abelian complexity in infinite words is a combinatorial tool which developed essentially during the last five years. In this paper, we undertake to establish connections between abelian complexity and uniform frequencies in infinite words. In particular, we focus on the binary case to link uniform equi-frequency with abelian complexity. We also provide various examples of infinite words to illustrate the absence of connection between usual complexity and abelian complexity. Some properties involving uniform recurrence are also given.

  • articleNo Access

    The Overlap Gap Between Left-Infinite and Right-Infinite Words

    We study ultimate periodicity properties related to overlaps between the suffixes of a left-infinite word λ and the prefixes of a right-infinite word ρ. The main theorem states that the set of minimum lengths of words x and x such that xλn=ρnx or λnx=xρn is finite, where n runs over positive integers and λn and ρn are respectively the suffix of λ and the prefix of ρ of length n, if and only if λ and ρ are ultimately periodic words of the form λ=uv and ρ=wu for some finite words u, v and w.

  • articleNo Access

    TAMENESS OF THE PSEUDOVARIETY LS1

    The notion of κ-tameness of a pseudovariety was introduced by Almeida and Steinberg and is a strong property which implies decidability of pseudovarieties. In this paper we prove that the pseudovariety LSl, of local semilattices, is κ-tame.

  • articleNo Access

    COMPLETE REDUCIBILITY OF THE PSEUDOVARIETY LS1

    In this paper we prove that the pseudovariety LSl of local semilattices is completely κ-reducible, where κ is the implicit signature consisting of the multiplication and the ω-power. Informally speaking, given a finite equation system with rational constraints, the existence of a solution by pseudowords of the system over LSl implies the existence of a solution by κ-words of the system over LSl satisfying the same constraints.