Hasil untuk "cs.FL"

Francis Wlazinski

This article provides a reminder of some properties of primitive words and the morphisms that preserve them. Their proofs, which I have more or less revised, are included. This makes the article almost self-contained. I also contribute by giving some properties of primitive words, but especially by showing that a morphism without powers k($\ge$ 5) is primitive and that a uniform morphism without powers k($\ge$ 2) is primitive.

Javier Esparza, Mogens Nielsen

We survey 25 years of research on decidability issues for Petri nets. We collect results on the decidability of important properties, equivalence notions, and temporal logics.

Manfred Kufleitner

Parikh's Theorem says that the Parikh image of a context-free language is semilinear. We give a short proof of Parikh's Theorem using the formulation of Verma, Seidl, and Schwentick in terms of Presburger arithmetic. The proof relies on an Eulerian property of derivation trees of context-free languages and was inspired by Hierholzer's algorithm; it does not use the Chomsky normal form.

Dmitry Golubenko

Nonterminal complexity of a context-free language is the smallest possible number of nonterminals in its generating grammar. While in general case nonterminal complexity computation problem is unsolvable, it can be computed for different families of regular languages. In this paper we study nonterminal complexity of some families of infinite regular languages.

Peter Gacs

There are several proofs now for the stability of Toom's example of a two-dimensional stable cellular automaton and its application to fault-tolerant computation. Simon and Berman simplified and strengthened Toom's original proof: the present report is a simplified exposition of their proof.

Mikołaj Bojańczyk, Amina Doumane

We study tree-to-tree transformations that can be defined in first-order logic or monadic second-order logic. We prove a decomposition theorem, which shows that every transformation can be obtained from prime transformations, such as tree-to-tree homomorphisms or pre-order traversal, by using combinators such as function composition.

Anca Muscholl, Gabriele Puppis

In this paper we provide a positive answer to a question left open by Alur and and Deshmukh in 2011 by showing that equivalence of finite-valued copyless streaming string transducers is decidable.

Michiel de Bondt

We compute all synchronizing DFAs with 7 states and synchronization length >= 29. Furthermore, we compute alphabet size ranges for maximal, minimal and semi-minimal synchronizing DFAs with up to 7 states.

Michiel de Bondt

We give a short proof of a theorem of J.-E. Pin (theorem 1.1 below), which can be found in his thesis. The part of the proof which is my own (not Pin's) is a complete replacement of the same part in an earlier version of this paper.

Thomas Place, Marc Zeitoun

In the theory of formal languages, the understanding of concatenation hierarchies of regular languages is one of the most fundamental and challenging topic. In this paper, we survey progress made in the comprehension of this problem since 1971, and we establish new generic statements regarding this problem.

Claudio Menghi, Paola Spoletini, Carlo Ghezzi

Software development is an iterative process which includes a set of development steps that transform the initial high level specification of the system into its final, fully specified, implementation. This report discusses the theoretical foundations that allow Incomplete Büchi Automata (IBAs) to be used in the iterative development of a sequential system.

Giacomo Marciani

In this paper, we prove the semidecidability of the problem of saying whether or not a context-free grammar generates a regular language. We introduce the notion of context-free grammar in Marciani Normal Form. We prove that a context-free grammar in Marciani Normal Form always generates a regular language.

Štěpán Holub, Mike Müller

We characterize binary words that have exactly two unbordered conjugates and show that they can be expressed as a product of two palindromes.

Chuan Guo, Jeffrey Shallit, Arseny M. Shur

We prove a number of results on the structure and enumeration of palindromes and antipalindromes. In particular, we study conjugates of palindromes, palindromic pairs, rich words, and the counterparts of these notions for antipalindromes.

Alexey Sorokin

In this paper we prove several results on normal forms for linear displacement context-free grammars. The results themselves are rather simple and use well-known techniques, but they are extensively used in more complex constructions. Therefore this article mostly serves educational and referential purposes.

Jelena Ignjatović, Miroslav Ćirić, Zorana Jančić

In this paper we prove the equivalence of sequential, Mealy-type and Moore-type weighted finite automata with output, with respect to various semantics which are defined here.

Stefan Kiefer

Given a basic process algebra (BPA) and two stack symbols, the BPA bisimilarity problem asks whether the two stack symbols are bisimilar. We show that this problem is EXPTIME-hard.

Zoltan Esik, Szabolcs Ivan

We consider context-free languages equipped with the lexicographic ordering. We show that when the lexicographic ordering of a context-free language is scattered, then its Hausdorff rank is less than $ω^ω$. As a corollary of this result we obtain that an ordinal is the order type of a well-ordered context-free language iff it is less than $ω^{ω^ω}$.

Wolfgang Steiner

The (-β)-integers are natural generalisations of the β-integers, and thus of the integers, for negative real bases. They can be described by infinite words which are fixed points of anti-morphisms. We show that they are not necessarily uniformly discrete and relatively dense in the real numbers.

Victor Yodaiken

This paper illustrates a technique for specifying the timing, logical operation, and compositional circuit design of digital circuits in terms of ordinary state machines with output (Moore machines). The method is illustrated here with specifications of gates, latches, and other simple circuits and via the construction of devices starting with a SR latch built from gates. The method is based on "classical" automata and recursive functions on strings (sequential functions).