1,721,013 research outputs found
The Operation ^ on Formal Series
No full textAbstractWe introduce a new operation over formal power series, which we denote by ↑. It is based on zigzag factorization of a word, i.e. factorizations obtained allowing some backward-coming in concatenation. This operation is not rational; moreover, the image of rational power series is not always algebraic. We represent power series by s↑ by two-way finite automata with multiplicity. For s∈RRat+《A《, we doubly characterize the rationality of the image s↑ and show its decidability
The Zig-Zag Power Series: A Two-Way Version of the * Operator
No full textAbstractThis paper deals with the zig-zag power series as introduced in [1], that is with a two-way version of the star (∗) operator over formal languages and power series. The main result is a double characterization of rationality of zig-zag power series by a condition over the structure of the starting language and another over some associated two-way automata. For rational zig-zag power series we present the construction of some one-way automata recognizing them
A Non-ambiguous Decomposition of Regular Languages and Factorizing Codes
No full textAbstractGiven languages Z,L⊆Σ∗,Z is L-decomposable (finitely L-decomposable, resp.) if there exists a non-trivial pair of languages (finite languages, resp.) (A,B), such that Z=AL+B and the operations are non-ambiguous. We show that it is decidable whether Z is L-decomposable and whether Z is finitely L-decomposable, in the case Z and L are regular languages. The result in the case Z=L allows one to decide whether, given a finite language S⊆Σ∗, there exist finite languages C,P such that SC∗P=Σ∗ with non-ambiguous operations. This problem is related to Schützenberger's Factorization Conjecture on codes. We also construct an infinite family of factorizing codes
Sur les Codes ZigZag et Leur Décidabilité
No full textAbstractThis paper deals with zigzag factorizations and zigzag codes. The language of “zigzag” over a regular language is represented by constructing a special family of two-way automata. Decidability of zigzag codes, previously shown for the finite languages, is proved here for all regular languages by the analysis of the set of “crossing sequences” produced by a two-way automation in the family. We also obtain that it is decidable whether or not a two-way automation of a certain type is non-ambiguous.RésuméDans ce papier on reprend les notions de factorisation zigzag et de code zigzag. On construit pour tout langage rationnel, une famille d'automates bilatéres lesquels reconnaissent les mots obtenus “par zigzag” sur le langage. La décidabilité des codes zigzag, qui avait été prouvée pour les langages finis, est démontrée ici pour tout langage rationnel, en analysant les “suites de traversée” (crossing sequences) engendrées par un automate bilatère de la famille. Une conséquence est la décidabilité de la non-ambiguité des automates bilatères d'un certain type
Two-dimensional comma-free and cylindric codes
Full text linkA two-dimensional code of pictures is defined as a set X⊆Σ⁎⁎ such that any picture over Σ is tilable in at most one way with pictures in X. It has been proved that it is undecidable whether a finite set of pictures is a code. Here we introduce two classes of picture codes: the comma-free codes and the cylindric codes, with the aim of generalizing the definitions of comma-free (or self-synchronizing) code and circular code of strings. The properties of these classes are studied and compared, in particular in relation to maximality and completeness. As a byproduct, we introduce self-covering pictures and study their periodicity issues
- …
