Page 1 Next

Displaying 1 – 20 of 24

Showing per page

A coalgebraic view on reachability

Thorsten Wißmann, Stefan Milius, Shin-ya Katsumata, Jérémy Dubut (2019)

Commentationes Mathematicae Universitatis Carolinae

Coalgebras for an endofunctor provide a category theoretic framework for modeling a wide range of state-based systems of various types. We provide an iterative construction of the reachable part of a given pointed coalgebra that is inspired by and resembles the standard breadth-first search procedure to compute the reachable part of a graph. We also study coalgebras in Kleisli categories: for a functor extending a functor on the base category, we show that the reachable part of a given pointed coalgebra...

Antiassociative groupoids

Milton Braitt, David Hobby, Donald Silberger (2017)

Mathematica Bohemica

Given a groupoid G , , and k 3 , we say that G is antiassociative if an only if for all x 1 , x 2 , x 3 G , ( x 1 x 2 ) x 3 and x 1 ( x 2 x 3 ) are never equal. Generalizing this, G , is k -antiassociative if and only if for all x 1 , x 2 , ... , x k G , any two distinct expressions made by putting parentheses in x 1 x 2 x 3 x k are never equal. We prove that for every k 3 , there exist finite groupoids that are k -antiassociative. We then generalize this, investigating when other pairs of groupoid terms can be made never equal.

Commutative images of rational languages and the abelian kernel of a monoid

Manuel Delgado (2001)

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

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 of the algorithm...

Commutative images of rational languages and the Abelian kernel of a monoid

Manuel Delgado (2010)

RAIRO - Theoretical Informatics and Applications

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 of the algorithm...

On Multiset Ordering

Grzegorz Bancerek (2016)

Formalized Mathematics

Formalization of a part of [11]. Unfortunately, not all is possible to be formalized. Namely, in the paper there is a mistake in the proof of Lemma 3. It states that there exists x ∈ M1 such that M1(x) > N1(x) and (∀y ∈ N1)x ⊀ y. It should be M1(x) ⩾ N1(x). Nevertheless we do not know whether x ∈ N1 or not and cannot prove the contradiction. In the article we referred to [8], [9] and [10].

One-way communication complexity of symmetric boolean functions

Jan Arpe, Andreas Jakoby, Maciej Liśkiewicz (2005)

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

We study deterministic one-way communication complexity of functions with Hankel communication matrices. Some structural properties of such matrices are established and applied to the one-way two-party communication complexity of symmetric Boolean functions. It is shown that the number of required communication bits does not depend on the communication direction, provided that neither direction needs maximum complexity. Moreover, in order to obtain an optimal protocol, it is in any case sufficient...

One-way communication complexity of symmetric Boolean functions

Jan Arpe, Andreas Jakoby, Maciej Liśkiewicz (2010)

RAIRO - Theoretical Informatics and Applications

We study deterministic one-way communication complexity of functions with Hankel communication matrices. Some structural properties of such matrices are established and applied to the one-way two-party communication complexity of symmetric Boolean functions. It is shown that the number of required communication bits does not depend on the communication direction, provided that neither direction needs maximum complexity. Moreover, in order to obtain an optimal protocol, it is in any case sufficient...

Currently displaying 1 – 20 of 24

Page 1 Next