Luca Aceto, Zoltán Ésik, Anna Ingólfsdóttir (2002)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
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.
Ondřej Klíma, Libor Polák (2008)
RAIRO - Theoretical Informatics and Applications
Similarity:
A language is literally idempotent in case that if and only if , for each , . Varieties of literally idempotent languages result naturally by taking all literally idempotent languages in a classical (positive) variety or by considering a certain closure operator on classes of languages. We initiate the systematic study of such varieties. Various classes of literally idempotent languages can be characterized using syntactic methods. A starting example is the class of all finite unions...
Jürgen Dassow, Victor Mitrana, Gheorghe Păun, Ralf Stiebe (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
We introduce the notion of a differentiation function of a context-free grammar which gives the number of terminal words that can be derived in a certain number of steps. A grammar is called narrow (or -narrow) iff its differentiation function is bounded by a constant (by ). We present the basic properties of differentiation functions, especially we relate them to structure function of context-free languages and narrow grammars to slender languages. We discuss the decidability...
Syed A. Huq (1973)
Colloquium Mathematicae
Similarity:
Ines Klimann (2003)
Kybernetika
Similarity:
In this article, we compare different types of representations for series with coefficients in complete idempotent semirings. Each of these representations was introduced to solve a particular problem. We show how they are or are not included one in the other and we present a common generalization of them.
David Stanovsky (2009)
Rendiconti del Seminario Matematico della Università di Padova
Similarity:
Manuel Delgado (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
Natural algorithms to compute rational expressions for recognizable languages, even those which work well in practice, may produce very long expressions. So, aiming towards the computation of the commutative image of a recognizable language, one should avoid passing through an expression produced this way. We modify here one of those algorithms in order to compute directly a semilinear expression for the commutative image of a recognizable language. We also give a second modification...
Ratti, J.S., Lin, Y.F. (1989)
International Journal of Mathematics and Mathematical Sciences
Similarity: