A formal power series φ with a real cut point λ defines the language L_{φ,λ} = {ω ∈ Σ∗ | |φ(ω) > λ}; λ is called isolated if inf_ω |φ(ω) − λ| > 0. In this paper we give conditions for guaranteeing the regularity of L_{φ,λ}, with λ isolated, for two classes of formal series: rational series and Hadamard quotients of rational series. Finally, we provide an explicit representation of the behavior of a subclass of two-way weighted automata in terms of Hadamard quotient of rational series.
Regularity of languages defined by formal series with isolated cut point / A. Bertoni, M.P. Bianchi, F. D'Alessandro - In: Third workshop on non-classical models for automata and applications - NCMA 2011 : Milan, Italy, july 18-19, 2011 : proceedings / [a cura di] R. Freund, Markus Holzer, C. Mereghetti, F. Otto, B. Palano. - Vienna : Austrian Computer Society, 2011. - ISBN 9783854032823. - pp. 73-87 (( Intervento presentato al 3. convegno Workshop on Non-Classical Models for Auomata and Applications tenutosi a Milan, Italy nel 2011.
Titolo: | Regularity of languages defined by formal series with isolated cut point |
Autori: | |
Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
Data di pubblicazione: | 2011 |
Tipologia: | Book Part (author) |
Appare nelle tipologie: | 03 - Contributo in volume |