Identities in upper triangular tropical matrix semigroups and the bicyclic monoid

Autor: Marianne Johnson, Laure Daviaud, Mark Kambites

Publikováno v: Daviaud, L, Johnson, M & Kambites, M 2018, ' IDENTITIES IN UPPER TRIANGULAR TROPICAL MATRIX SEMIGROUPS AND THE BICYCLIC MONOID ', Journal of Algebra, vol. 501, pp. 503-525 . https://doi.org/10.1016/j.jalgebra.2017.12.032

We establish necessary and sufficient conditions for a semigroup identity to hold in the monoid of $n\times n$ upper triangular tropical matrices, in terms of equivalence of certain tropical polynomials. This leads to an algorithm for checking whethe

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::18fcf0d0d6e9f8d3faa47dd460b885be
https://doi.org/10.1016/j.jalgebra.2017.12.032

Classes of languages generated by the Kleene star of a word

Autor: Laure Daviaud, Charles Paperman

Publikováno v: Information and Computation
Information and Computation, 2018, 262 (Part 1), pp.90-109. ⟨10.1016/j.ic.2018.07.002⟩
Information and Computation, Elsevier, 2018, 262 (Part 1), pp.90-109. ⟨10.1016/j.ic.2018.07.002⟩
MFCS (1)
Mathematical Foundations of Computer Science 2015 ISBN: 9783662480564

International audience; In this paper, we study the lattice and the Boolean algebra, possibly closed under quotient, generated by the languages of the form $u⁎$, where $u$ is a word. We provide effective equational characterisations of these classe

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c897eba835298addde59e3521ddd8fd9
http://wrap.warwick.ac.uk/104953/8/WRAP-classes-languages-generated-Kleene-star-Daviaud-2018.pdf

Regular and First-Order List Functions

Autor: Laure Daviaud, Mikołaj Bojańczyk, Shankara Narayanan Krishna

Publikováno v: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science -LICS '18
Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science-LICS 18
Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science
LICS

We define two classes of functions, called regular (respectively, first- order) list functions , which manipulate objects such as lists, lists of lists, pairs of lists, lists of pairs of lists, etc. The definition is in the style of regular expressio

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bb9ad69829f01814fe00c550318aac6d

Approximate Comparison of Functions Computed by Distance Automata

Autor: Laure Daviaud, Thomas Colcombet

Distance automata are automata weighted over the semiring (??{?},min,+)$(\mathbb {N}\cup \{\infty \},\min , +)$ (the tropical semiring). Such automata compute functions from words to ??{?}$\mathbb {N}\cup \{\infty \}$. It is known from Krob that the

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::dd6ae87e67de8f056e45a606c0cc109f
https://openaccess.city.ac.uk/id/eprint/21296/1/version_journal_v3.pdf

Size-Change Abstraction and Max-Plus Automata

Autor: Laure Daviaud, Florian Zuleger, Thomas Colcombet

Publikováno v: Mathematical Foundations of Computer Science 2014 ISBN: 9783662445211
MFCS (1)

Max-plus automata (over ℕ ∪ − ∞) are finite devices that map input words to non-negative integers or − ∞. In this paper we present (a) an algorithm allowing to compute the asymptotic behaviour of max-plus automata, and (b) an application

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::879141a2296c9ed5e4487109243c1dcd
https://openaccess.city.ac.uk/id/eprint/21300/1/main_max_plus.pdf