On quotients of formal power series

Li, Y; Wang, Q; Li, S

On quotients of formal power series

Li, Y Wang, Q Li, S

Permalink

Publisher:: ACADEMIC PRESS INC ELSEVIER SCIENCE
Publication Type:: Journal Article
Citation:: Information and Computation, 2022, 285
Issue Date:: 2022-05-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

The embargo period expires on 1 May 2024

Adobe PDF

Download Accepted versionAdobe PDF (307.27 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Li, Y
dc.contributor.author	Wang, Q
dc.contributor.author	Li, S https://orcid.org/0000-0002-3332-2546
dc.date.accessioned	2023-02-22T05:07:36Z
dc.date.available	2023-02-22T05:07:36Z
dc.date.issued	2022-05-01
dc.identifier.citation	Information and Computation, 2022, 285
dc.identifier.issn	0890-5401
dc.identifier.issn	1090-2651
dc.identifier.uri	http://hdl.handle.net/10453/166320
dc.description.abstract	Quotient is a basic operation of formal languages, which plays a key role in the construction of minimal deterministic finite automata (DFA) and the universal automata. In this paper, we extend this operation to formal power series and systemically investigate its implications in the study of weighted automata. In particular, we define two quotient operations for formal power series which are called (left or right) quotients and (left or right) residuals respectively. Algebraic properties of the quotient operation and closure properties (w.r.t. regular and context-free series) under quotients and residuals are also investigated for formal power series. Using these operations, we define for each formal power series A two weighted automata that accept A. The first is the minimal deterministic weighted automaton of A, and the second is the universal weighted automaton of A. An effective algebraic method to construct the universal automaton is also presented.
dc.language	English
dc.publisher	ACADEMIC PRESS INC ELSEVIER SCIENCE
dc.relation.ispartof	Information and Computation
dc.relation.isbasedon	10.1016/j.ic.2022.104874
dc.rights	info:eu-repo/semantics/embargoedAccess
dc.subject	08 Information and Computing Sciences
dc.subject.classification	Computation Theory & Mathematics
dc.title	On quotients of formal power series
dc.type	Journal Article
utslib.citation.volume	285
utslib.for	08 Information and Computing Sciences
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	open_access	*
utslib.copyright.embargo	2024-05-01T00:00:00+1000Z
dc.date.updated	2023-02-22T05:07:35Z
pubs.publication-status	Published
pubs.volume	285

Abstract:

Quotient is a basic operation of formal languages, which plays a key role in the construction of minimal deterministic finite automata (DFA) and the universal automata. In this paper, we extend this operation to formal power series and systemically investigate its implications in the study of weighted automata. In particular, we define two quotient operations for formal power series which are called (left or right) quotients and (left or right) residuals respectively. Algebraic properties of the quotient operation and closure properties (w.r.t. regular and context-free series) under quotients and residuals are also investigated for formal power series. Using these operations, we define for each formal power series A two weighted automata that accept A. The first is the minimal deterministic weighted automaton of A, and the second is the universal weighted automaton of A. An effective algebraic method to construct the universal automaton is also presented.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/166320