On redundancy in simple temporal networks

Lee, JH; Li, S; Long, Z; Sioutis, M

On redundancy in simple temporal networks

Lee, JH

Li, S

Long, Z

Sioutis, M

Permalink

Publication Type:: Conference Proceeding
Citation:: Frontiers in Artificial Intelligence and Applications, 2016, 285 pp. 828 - 836
Issue Date:: 2016-01-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted Manuscript versionAdobe PDF (315.97 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Lee, JH https://orcid.org/0000-0001-9840-780X	en_US
dc.contributor.author	Li, S https://orcid.org/0000-0002-3332-2546	en_US
dc.contributor.author	Long, Z https://orcid.org/0000-0002-2714-3453	en_US
dc.contributor.author	Sioutis, M https://orcid.org/0000-0001-7562-2443	en_US
dc.date.issued	2016-01-01	en_US
dc.identifier.citation	Frontiers in Artificial Intelligence and Applications, 2016, 285 pp. 828 - 836	en_US
dc.identifier.isbn	9781614996712	en_US
dc.identifier.issn	0922-6389	en_US
dc.identifier.uri	http://hdl.handle.net/10453/80715
dc.description.abstract	© 2016 The Authors and IOS Press. The Simple Temporal Problem (STP) has been widely used in various applications to schedule tasks. For dynamical systems, scheduling needs to be efficient and flexible to handle uncertainty and perturbation. To this end, modern approaches usually encode the temporal information as an STP instance. This representation contains redundant information, which can not only take a significant amount of storage space, but also make scheduling inefficient due to the non-concise representation. In this paper, we investigate the problem of simplifying an STP instance by removing redundant information. We show that such a simplification can result in a unique minimal representation without loss of temporal information, and present an efficient algorithm to achieve this task. Evaluation on a large benchmark dataset of STP exhibits a significant reduction in redundant information for the involved instances.	en_US
dc.relation	http://purl.org/au-research/grants/arc/DP120104159
dc.relation.ispartof	Frontiers in Artificial Intelligence and Applications	en_US
dc.relation.isbasedon	10.3233/978-1-61499-672-9-828	en_US
dc.title	On redundancy in simple temporal networks	en_US
dc.type	Conference Proceeding
utslib.citation.volume	285	en_US
utslib.for	170203 Knowledge Representation and Machine Learning	en_US
utslib.for	0801 Artificial Intelligence and Image Processing	en_US
pubs.embargo.period	Not known	en_US
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
pubs.organisational-group	/University of Technology Sydney/Students
utslib.copyright.status	open_access
pubs.publication-status	Published	en_US
pubs.volume	285	en_US

Abstract:

© 2016 The Authors and IOS Press. The Simple Temporal Problem (STP) has been widely used in various applications to schedule tasks. For dynamical systems, scheduling needs to be efficient and flexible to handle uncertainty and perturbation. To this end, modern approaches usually encode the temporal information as an STP instance. This representation contains redundant information, which can not only take a significant amount of storage space, but also make scheduling inefficient due to the non-concise representation. In this paper, we investigate the problem of simplifying an STP instance by removing redundant information. We show that such a simplification can result in a unique minimal representation without loss of temporal information, and present an efficient algorithm to achieve this task. Evaluation on a large benchmark dataset of STP exhibits a significant reduction in redundant information for the involved instances.

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

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