Hasil untuk "cs.FL"

Gerard Memmi

In this short note, we are interested in discussing characteristics of finite generating sets for $\mathcal{F}$, the set of all semiflows with non negative coefficients of a Petri Net. By systematically positioning these results over semi rings such as $\mathbb{N}$ or $\mathbb{Q^+}$ then over a field such as $\mathbb{Q}$, we were able to discover a handful of new results

Ernst-Erich Doberkat

Congruences for stochastic automata are defined, the correspondin factor automata are constructed and investigated for automata ove analytic spaces. We study the behavior under finite and infinite streams. Congruences consist of multiple parts, it is shown that factoring can be done in multiple steps, guided by these parts.

James D. Currie

Let $S$ be one of $\{aba,bcb\}$ and $\{aba, aca\}$, and let $w$ be an infinite square-free word over $Σ=\{a,b,c\}$ with no factor in $S$. Suppose that $f:Σ\rightarrow T^*$ is a non-erasing morphism. Word $f(w)$ is square-free if and only if $f$ is square-free on factors of $w$ of length 8 or less.

Nicolás Álvarez, Olivier Carton

In this paper we consider the notion of normality of sequences in shifts of finite type. A sequence is normal if the frequency of each block exists and is equal to the Parry measure of the block. We give a characterization of normality in terms of incompressibility by lossless transducers. The result was already known in the case of the full shift.

Oleksiy Kurganskyy, Alexandra Maximova

This paper contains results related to synthesis and presentation of abstract automata by fragments of behaviour and investigates the structure of the classes of finite connected initial output-less automata specified by systems of defining relations considered as fragments, co-fragments, counter-fragments and co-counter-fragments of automata.

Kazuhiro Inaba

Given a finite alphabet $Σ$ and a deterministic finite automaton on $Σ$, the problem of determining whether the language recognized by the automaton contains any pangram is \NP-complete. Various other language classes and problems around pangrams are analyzed.

Vojtěch Vorel

We complete the initial study of jumping finite automata, which was started in a former article of Meduna and Zemek \citep{athMED1}. The open questions about basic closure properties are solved. Besides this, we correct erroneous results presented in the article. Finally, we point out important relations between jumping finite automata and some other models studied in the literature.

M. Grech, A. Kisielewicz

The Černý's conjecture states that for every synchronizing automaton with n states there exists a reset word of length not exceeding (n-11)^2. We prove this conjecture for a class of automata preserving certain properties of intervals of a directed graph. Our result unifies and generalizes some earlier results obtained by other authors.

Loris D'Antoni

In data languages the positions of strings and trees carry a label from a finite alphabet and a data value from an infinite alphabet. Extensions of automata and logics over finite alphabets have been defined to recognize data languages, both in the string and tree cases. In this paper we describe and compare the complexity and expressiveness of such models to understand which ones are better candidates as regular models.

Štěpán Holub

We show that paper folding words contain arbitrarily large abelian powers.

Roman Kolpakov

Combinatorial properties of maximal repetitions (runs) in formal words are studied. We classify all maximal repetitions in a word as primary and secondary where the set of all primary repetitions determines all the other repetitons in the word. Essential combinatorial properties of primary repetitions are established.

Jeffrey Shallit

We give another proof of a theorem of Fife - understood broadly as providing a finite automaton that gives a complete description of all infinite binary overlap-free words. Our proof is significantly simpler than those in the literature. As an application we give a complete characterization of the overlap-free words that are 2-automatic.

Margenstern Maurice

In this paper, we significantly improve a previous result by the same author showing the existence of a weakly universal cellular automaton with five states living in the hyperbolic 3D-space. Here, we get such a cellular automaton with three states only.

Yuan Gao, Sheng Yu

In this paper, we study the state complexities of union and intersection combined with star and reversal, respectively. We obtain the state complexities of these combined operations on regular languages and show that they are less than the mathematical composition of the state complexities of their individual participating operations.

Alexander Shen

We consider a problem of decomposition of a ternary function into a composition of binary ones from the viewpoint of communication complexity and algorithmic information theory as well as some applications to cellular automata.

Zoltan Esik, Werner Kuich

We consider algebras of rational power series over an alphabet $Σ$ with coefficients in a commutative semiring $K$ and characterize them as the free algebras in various classes of algebraic structures.

Ali Akbar Safilian, Farzad Didehvar

In this article we define a new reducibility based on the enumeration orders of r.e. sets.

Juha Honkala

We study the equality problem for infinite words obtained by iterating morphisms. In particular, we give a practical algorithm to decide whether or not two words generated by primitive morphisms are equal.

Benjamin Steinberg

The results of several papers concerning the Černý conjecture are deduced as consequences of a simple idea that I call the averaging trick. This idea is implicitly used in the literature, but no attempt was made to formalize the proof scheme axiomatically. Instead, authors axiomatized classes of automata to which it applies.

E. V. Pribavkina

Using combinatorial properties of incomplete sets in a free monoid we construct a series of n-state deterministic automata with zero whose shortest synchronizing word has length n^2/4+n/2-1.