The Library
Stamina : stabilisation nonoids in automata theory
Tools
Fijalkow, Nathanael, Gimbert, Hugo, Kelmendi, Edon and Kuperberg, Denis (2017) Stamina : stabilisation nonoids in automata theory. In: 22nd International Conference Implementation and Application of Automata, 27-30 Jun 2017, Université Paris-Est Marne-la-Vallée. Published in: Implementation and Application of Automata ISBN 9783319601335. doi:10.1007/978-3-319-60134-2_9 ISSN 0302-9743.
|
PDF
WRAP-stamina-monoids-automata-Fijalkow-.pdf - Accepted Version - Requires a PDF viewer. Download (632Kb) | Preview |
Official URL: https://doi.org/10.1007/978-3-319-60134-2_9
Abstract
We present Stamina, a tool solving three algorithmic problems in automata theory. First, compute the star height of a regular language, i.e. the minimal number of nested Kleene stars needed for expressing the language with a complement-free regular expression. Second, decide limitedness for regular cost functions. Third, decide whether a probabilistic leaktight automaton has value 1, i.e. whether a probabilistic leaktight automaton accepts words with probability arbitrarily close to 1.
All three problems reduce to the computation of the stabilisation monoid associated with an automaton, which is computationally challenging because the monoid is exponentially larger than the automaton. The compact data structures used in Stamina, together with optimisations and heuristics, allow us to handle automata with several hundreds of states.
This radically improves upon the performances of ACME, a similar tool solving a subset of these problems.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Machine theory, Monoids | ||||||
Series Name: | Lecture Notes in Computer Science | ||||||
Journal or Publication Title: | Implementation and Application of Automata | ||||||
Publisher: | Springer International Publishing | ||||||
ISBN: | 9783319601335 | ||||||
ISSN: | 0302-9743 | ||||||
Official Date: | 2017 | ||||||
Dates: |
|
||||||
DOI: | 10.1007/978-3-319-60134-2_9 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Date of first compliant deposit: | 2 May 2017 | ||||||
Date of first compliant Open Access: | 2 May 2017 | ||||||
Funder: | Engineering and Physical Sciences Research Council (EPSRC), Alan Turing Institute (London, England), Agence nationale de recherches sur le SIDA (France) (ANRS) | ||||||
Grant number: | EP/N510129/1 (EPSRC), Project “Stoch-MC” and “LaBEX CPU” (ANRS) | ||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | 22nd International Conference Implementation and Application of Automata | ||||||
Type of Event: | Conference | ||||||
Location of Event: | 27-30 Jun 2017 | ||||||
Date(s) of Event: | Université Paris-Est Marne-la-Vallée | ||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year