Fast computations on ordered nominal sets
| العنوان: | Fast computations on ordered nominal sets |
|---|---|
| المؤلفون: | Venhoek, D., Moerman, J., Rot, J., Fischer, B. |
| المساهمون: | Fischer, B., RS-Research Program Towards High-Quality and Intelligent Software (THIS), Department of Computer Science |
| المصدر: | Fischer, B. (ed.), Theoretical Aspects of Computing – ICTAC 2018: 15th International Colloquium, Stellenbosch, South Africa, October 16–19, 2018, Proceedings, pp. 493-512 Theor. Comput. Sci., 935, 82-104. Elsevier Theoretical Computer Science, 935, pp. 82-104 Theoretical Computer Science, 935, 82-104 Open Universiteit Venhoek, D, Moerman, J & Rot, J 2022, ' Fast computations on ordered nominal sets ', Theor. Comput. Sci., vol. 935, pp. 82-104 . https://doi.org/10.1016/j.tcs.2022.09.002 Fischer, B. (ed.), Theoretical Aspects of Computing – ICTAC 2018: 15th International Colloquium, Stellenbosch, South Africa, October 16–19, 2018, Proceedings, 493-512. Cham : Springer International Publishing STARTPAGE=493;ENDPAGE=512;ISSN=0302-9743;TITLE=Fischer, B. (ed.), Theoretical Aspects of Computing – ICTAC 2018: 15th International Colloquium, Stellenbosch, South Africa, October 16–19, 2018, Proceedings |
| بيانات النشر: | Elsevier BV, 2022. |
| سنة النشر: | 2022 |
| مصطلحات موضوعية: | FOS: Computer and information sciences, Computer Science - Logic in Computer Science, General Computer Science, ComputingMethodologies_DOCUMENTANDTEXTPROCESSING, Automata learning, Software Science, Minimisation, Nominal sets, Computer Science::Formal Languages and Automata Theory, Logic in Computer Science (cs.LO), Automata theory, Theoretical Computer Science |
| الوصف: | Nominal automata are models for recognising languages over infinite alphabets, based on the algebraic notion of nominal set. Motivated by their use in automata theory, we show how to compute efficiently with nominal sets over the so-called total order symmetry, a variant which allows to compare alphabet letters for equality as well as their respective order. We develop an explicit finite representation of such nominal sets and basic constructions thereon. The approach is implemented as the library Ons (Ordered Nominal Sets), enabling programming with infinite sets. Returning to our motivation of nominal automata, we evaluate Ons in two applications: minimisation of automata and active automata learning. In both cases, Ons is competitive compared to existing implementations and outperforms them for certain classes of inputs. |
| وصف الملف: | application/pdf |
| تدمد: | 0304-3975 0302-9743 |
| DOI: | 10.1016/j.tcs.2022.09.002 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::639712b9c358129a07e775e344e43366 https://doi.org/10.1016/j.tcs.2022.09.002 |
| Rights: | OPEN |
| رقم الانضمام: | edsair.doi.dedup.....639712b9c358129a07e775e344e43366 |
| قاعدة البيانات: | OpenAIRE |
| تدمد: | 03043975 03029743 |
|---|---|
| DOI: | 10.1016/j.tcs.2022.09.002 |