Streckenförmigkeit - eine weitere Verallgemeinerung der Sternförmigkeit
String Assembling Systems
We introduce and investigate string assembling systems which form a computational model that generates strings from copies out of a finite set of assembly units. The underlying mechanism is based on piecewise assembly of a double-stranded sequence of symbols, where the upper and lower strand have to match. The generation is additionally controlled by the requirement that the first symbol of a unit has to be the same as the last symbol of the strand generated so far, as well as by the distinction...
String Assembling Systems
We introduce and investigate string assembling systems which form a computational model that generates strings from copies out of a finite set of assembly units. The underlying mechanism is based on piecewise assembly of a double-stranded sequence of symbols, where the upper and lower strand have to match. The generation is additionally controlled by the requirement that the first symbol of a unit has to be the same as the last symbol of the strand generated so far, as well as by the distinction...
String distances and intrusion detection: Bridging the gap between formal languages and computer security
In this paper we analyze some intrusion detection strategies proposed in the literature and we show that they represent the various facets of a well known formal languages problem: computing the distance between a string x and a language L. In particular, the main differences among the various approaches adopted for building intrusion detection systems can be reduced to the characteristics of the language L and to the notion of distance adopted. As a further contribution we will also show that from...
Strong endomorphisms of TT-connected automata
Strong functors and interleaving fixpoints in game semantics
We describe a sequent calculus μLJ with primitives for inductive and coinductive datatypes and equip it with reduction rules allowing a sound translation of Gödel’s system T. We introduce the notion of a μ-closed category, relying on a uniform interpretation of open μLJ formulas as strong functors. We show that any μ-closed category is a sound model for μLJ. We then turn to the construction of a concrete μ-closed category based on Hyland-Ong game semantics. The model relies on three main ingredients:...
Strong iterative pairs and the regularity of context-free languages
Strongly locally testable semigroups with commuting idempotents and related languages
Strongly locally testable semigroups with commuting idempotents and related languages
If we consider words over the alphabet which is the set of all elements of a semigroup S, then such a word determines an element of S: the product of the letters of the word. S is strongly locally testable if whenever two words over the alphabet S have the same factors of a fixed length k, then the products of the letters of these words are equal. We had previously proved [19] that the syntactic semigroup of a rational language L is strongly locally testable if and only if L is both locally...
Structural unambiguity of formal languages
Structure de l'automate plein, réduit et inversible
Structured redundancy for fault tolerance in state-space models and Petri nets
The design and implementation of systems in state form has traditionally focused on minimal representations which require the least number of state variables. However, “structured redundancy” – redundancy that has been intentionally introduced in some systematic way – can be extremely important when fault tolerance is desired. The redundancy can be used to detect and correct errors or to guarantee desirable performance despite hardware or computational failures. Modular redundancy, the traditional...
Study of irreducible balanced pairs for substitutive languages
Let be a language. A balanced pair (u,v) consists of two words u and v in which have the same number of occurrences of each letter. It is irreducible if the pairs of strict prefixes of u and v of the same length do not form balanced pairs. In this article, we are interested in computing the set of irreducible balanced pairs on several cases of languages. We make connections with the balanced pairs algorithm and discrete geometrical constructions related to substitutive languages. We characterize...
Studying graph - stability to apprehend relative hardness of constructive-non-constructive approximation
Sturmian morphisms. (Morphismes de Sturm.)
Sublogarithmic -space is not closed under complement and other separation results
Substitution systems associated with the dynamical system (𝒜, Tf)*
We consider the dynamical system (𝒜, Tf), where 𝒜 is a class of differential real functions defined on some interval and Tf : 𝒜 → 𝒜 is an operator Tfφ := fοφ, where f is a differentiable m-modal map. If we consider functions in 𝒜 whose critical values are periodic points for f then, we show how to define and characterize a substitution system associated with (𝒜, Tf). For these substitution systems, we compute the growth rate of the...
Substitution up to isomorphism
Substitutions, abstract number systems and the space filling property
In this paper we study multi-dimensional words generated by fixed points of substitutions by projecting the integer points on the corresponding broken halfline. We show for a large class of substitutions that the resulting word is the restriction of a linear function modulo and that it can be decided whether the resulting word is space filling or not. The proof uses lattices and the abstract number system associated with the substitution.
Subtree Matching by Pushdown Automata