Page 1 Next

Displaying 1 – 20 of 186

Showing per page

5-abelian cubes are avoidable on binary alphabets

Robert Mercaş, Aleksi Saarela (2014)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

A k-abelian cube is a word uvw, where the factors u, v, and w are either pairwise equal, or have the same multiplicities for every one of their factors of length at most k. Previously it has been shown that k-abelian cubes are avoidable over a binary alphabet for k ≥ 8. Here it is proved that this holds for k ≥ 5.

A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata

Daniel Kirsten (2008)

RAIRO - Theoretical Informatics and Applications

We show that the termination of Mohri's algorithm is decidable for polynomially ambiguous weighted finite automata over the tropical semiring which gives a partial answer to a question by Mohri [29]. The proof relies on an improvement of the notion of the twins property and a Burnside type characterization for the finiteness of the set of states produced by Mohri's algorithm.

A characterization of poly-slender context-free languages

Lucian Ilie, Grzegorz Rozenberg, Arto Salomaa (2010)

RAIRO - Theoretical Informatics and Applications

For a non-negative integer k, we say that a language L is k-poly-slender if the number of words of length n in L is of order 𝒪 ( n k ) . We give a precise characterization of the k-poly-slender context-free languages. The well-known characterization of the k-poly-slender regular languages is an immediate consequence of ours.

A classification of rational languages by semilattice-ordered monoids

Libor Polák (2004)

Archivum Mathematicum

We prove here an Eilenberg type theorem: the so-called conjunctive varieties of rational languages correspond to the pseudovarieties of finite semilattice-ordered monoids. Taking complements of members of a conjunctive variety of languages we get a so-called disjunctive variety. We present here a non-trivial example of such a variety together with an equational characterization of the corresponding pseudovariety.

A coalgebraic semantics of subtyping

Erik Poll (2001)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Coalgebras have been proposed as formal basis for the semantics of objects in the sense of object-oriented programming. This paper shows that this semantics provides a smooth interpretation for subtyping, a central notion in object-oriented programming. We show that different characterisations of behavioural subtyping found in the literature can conveniently be expressed in coalgebraic terms. We also investigate the subtle difference between behavioural subtyping and refinement.

A Coalgebraic Semantics of Subtyping

Erik Poll (2010)

RAIRO - Theoretical Informatics and Applications

Coalgebras have been proposed as formal basis for the semantics of objects in the sense of object-oriented programming. This paper shows that this semantics provides a smooth interpretation for subtyping, a central notion in object-oriented programming. We show that different characterisations of behavioural subtyping found in the literature can conveniently be expressed in coalgebraic terms. We also investigate the subtle difference between behavioural subtyping and refinement.

A fully equational proof of Parikh’s theorem

Luca Aceto, Zoltán Ésik, Anna Ingólfsdóttir (2002)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We show that the validity of Parikh’s theorem for context-free languages depends only on a few equational properties of least pre-fixed points. Moreover, we exhibit an infinite basis of μ -term equations of continuous commutative idempotent semirings.

A Fully Equational Proof of Parikh's Theorem

Luca Aceto, Zoltán Ésik, Anna Ingólfsdóttir (2010)

RAIRO - Theoretical Informatics and Applications

We show that the validity of Parikh's theorem for context-free languages depends only on a few equational properties of least pre-fixed points. Moreover, we exhibit an infinite basis of μ-term equations of continuous commutative idempotent semirings.

A Game Theoretical Approach to The Algebraic Counterpart of The Wagner Hierarchy : Part II

Jérémie Cabessa, Jacques Duparc (2009)

RAIRO - Theoretical Informatics and Applications

The algebraic counterpart of the Wagner hierarchy consists of a well-founded and decidable classification of finite pointed ω-semigroups of width 2 and height ωω. This paper completes the description of this algebraic hierarchy. We first give a purely algebraic decidability procedure of this partial ordering by introducing a graph representation of finite pointed ω-semigroups allowing to compute their precise Wagner degrees. The Wagner degree of any ω-rational language can therefore be computed...

A game theoretical approach to the algebraic counterpart of the Wagner hierarchy : Part I

Jérémie Cabessa, Jacques Duparc (2009)

RAIRO - Theoretical Informatics and Applications

The algebraic study of formal languages shows that ω-rational sets correspond precisely to the ω-languages recognizable by finite ω-semigroups. Within this framework, we provide a construction of the algebraic counterpart of the Wagner hierarchy. We adopt a hierarchical game approach, by translating the Wadge theory from the ω-rational language to the ω-semigroup context. More precisely, we first show that the Wagner degree is indeed a syntactic invariant. We then define a reduction relation on...

A generalized minimal realization theory of machines in a category.

Antonio Bahamonde (1983)

Stochastica

This paper presents a generalized minimal realization theory of machines in a category which contains the Kleiski case. The minimal realization is the cheapest realization for a given cost functor. The final reachable realization of Arbib and Manes ([5]) and the minimal state approach for nondeterministic machines are included here.

A Lower Bound For Reversible Automata

Pierre-Cyrille Héam (2010)

RAIRO - Theoretical Informatics and Applications

A reversible automaton is a finite automaton in which each letter induces a partial one-to-one map from the set of states into itself. We solve the following problem proposed by Pin. Given an alphabet A, does there exist a sequence of languages Kn on A which can be accepted by a reversible automaton, and such that the number of states of the minimal automaton of Kn is in O(n), while the minimal number of states of a reversible automaton accepting Kn is in O(ρn) for some ρ > 1? We give...

A sharpening of the Parikh mapping

Alexandru Mateescu, Arto Salomaa, Kai Salomaa, Sheng Yu (2001)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

In this paper we introduce a sharpening of the Parikh mapping and investigate its basic properties. The new mapping is based on square matrices of a certain form. The classical Parikh vector appears in such a matrix as the second diagonal. However, the matrix product gives more information about a word than the Parikh vector. We characterize the matrix products and establish also an interesting interconnection between mirror images of words and inverses of matrices.

A sharpening of the Parikh mapping

Alexandru Mateescu, Arto Salomaa, Kai Salomaa, Sheng Yu (2010)

RAIRO - Theoretical Informatics and Applications

In this paper we introduce a sharpening of the Parikh mapping and investigate its basic properties. The new mapping is based on square matrices of a certain form. The classical Parikh vector appears in such a matrix as the second diagonal. However, the matrix product gives more information about a word than the Parikh vector. We characterize the matrix products and establish also an interesting interconnection between mirror images of words and inverses of .

Algebraic and graph-theoretic properties of infinite n -posets

Zoltán Ésik, Zoltán L. Németh (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

A Σ -labeled n -poset is an (at most) countable set, labeled in the set Σ , equipped with n partial orders. The collection of all Σ -labeled n -posets is naturally equipped with n binary product operations and n ω -ary product operations. Moreover, the ω -ary product operations give rise to n ...

Algebraic and graph-theoretic properties of infinite n-posets

Zoltán Ésik, Zoltán L. Németh (2010)

RAIRO - Theoretical Informatics and Applications

A Σ-labeled n-poset is an (at most) countable set, labeled in the set Σ, equipped with n partial orders. The collection of all Σ-labeled n-posets is naturally equipped with n binary product operations and nω-ary product operations. Moreover, the ω-ary product operations give rise to nω-power operations. We show that those Σ-labeled n-posets that can be generated from the singletons by the binary and ω-ary product operations form the free algebra on Σ in a variety axiomatizable by an infinite collection...

Currently displaying 1 – 20 of 186

Page 1 Next