Cut Languages in Rational Bases

0467765 - ÚI 2017 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
Šíma, Jiří - Savický, Petr
Cut Languages in Rational Bases.
Language and Automata Theory and Applications. Cham: Springer, 2017 - (Drews, F.; Martín-Vide, C.; Truthe, B.), s. 311-322. Lecture Notes in Computer Science, 10168. ISBN 978-3-319-53732-0. ISSN 0302-9743.
[LATA 2017. International Conference on Language and Automata Theory and Applications /11./. Umea (SE), 06.03.2017-09.03.2017]
Grant CEP: GA ČR GBP202/12/G061
Institucionální podpora: RVO:67985807
Klíčová slova: grammars * quasi-periodic power series * cut language
Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

We introduce a so-called cut language which contains the representations of numbers in a rational base that are less than a given threshold. The cut languages can be used to refine the analysis of neural net models between integer and rational weights. We prove a necessary and sufficient condition when a cut language is regular, which is based on the concept of a quasi-periodic power series. For a nonnegative base and digits, we achieve a dichotomy that a cut language is either regular or non-context-free while examples of regular and non-context-free cut languages are presented. We show that any cut language with a rational threshold is context-sensitive.
Trvalý link: http://hdl.handle.net/11104/0265800