Timed automata and additive clock constraints

The subclass of linear hybrid automata which consists of time automata extended with additive clock constraints is investigated. A model is proved to be strictly more expressive than the basic one and the test for emptiness becomes undecidable. Results are extended to timed automata with only four c...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2000-07, Vol.75 (1), p.1-7
Main Authors: Bérard, Béatrice, Dufourd, Catherine
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Automata. Abstract machines. Turing machines
Computer science
control theory
systems
Decidability of emptiness
Exact sciences and technology
Real-time systems
Theoretical computing
Timed automata
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c367t-eab9927ab5efbfcc9f3a27b10c5a79e11622adb0408d9d25a6794445718ed2a83
cites cdi_FETCH-LOGICAL-c367t-eab9927ab5efbfcc9f3a27b10c5a79e11622adb0408d9d25a6794445718ed2a83
container_end_page 7
container_issue 1
container_start_page 1
container_title Information processing letters
container_volume 75
creator Bérard, Béatrice
Dufourd, Catherine
description The subclass of linear hybrid automata which consists of time automata extended with additive clock constraints is investigated. A model is proved to be strictly more expressive than the basic one and the test for emptiness becomes undecidable. Results are extended to timed automata with only four clocks and a restricted form of additive constraints.
doi_str_mv 10.1016/S0020-0190(00)00075-2
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_27771571</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0020019000000752</els_id><sourcerecordid>27771571</sourcerecordid><originalsourceid>FETCH-LOGICAL-c367t-eab9927ab5efbfcc9f3a27b10c5a79e11622adb0408d9d25a6794445718ed2a83</originalsourceid><addsrcrecordid>eNqFkM1LAzEQxYMoWKt_grAHET2sTrIf2ZxEil9Q8GA9h9lkFqLb3ZqkBf97Uyt6FAaGgd-bx3uMnXK44sDr6xcAATlwBRcAlwAgq1zssQlvpMhrztU-m_wih-wohLcE1WUhJyxfuCXZDNdxXGLEDId0WOui21Bm-tG8Z2YcQvTohhiO2UGHfaCTnz1lr_d3i9ljPn9-eJrdznNT1DLmhK1SQmJbUdd2xqiuQCFbDqZCqYjzWgi0LZTQWGVFhbVUZVlWkjdkBTbFlJ3v_q78-LGmEPXSBUN9jwON66CFlJInPIHVDjR-DMFTp1feLdF_ag56W47-Lkdvk2vYTipHi6Q7-zHAYLDvPA7GhT9xWTV1UybsZodRCrtx5HUwjgZD1nkyUdvR_WP0BYX-d24</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>27771571</pqid></control><display><type>article</type><title>Timed automata and additive clock constraints</title><source>ScienceDirect Freedom Collection</source><source>Backfile Package - Computer Science (Legacy) [YCS]</source><source>Backfile Package - Mathematics (Legacy) [YMT]</source><creator>Bérard, Béatrice ; Dufourd, Catherine</creator><creatorcontrib>Bérard, Béatrice ; Dufourd, Catherine</creatorcontrib><description>The subclass of linear hybrid automata which consists of time automata extended with additive clock constraints is investigated. A model is proved to be strictly more expressive than the basic one and the test for emptiness becomes undecidable. Results are extended to timed automata with only four clocks and a restricted form of additive constraints.</description><identifier>ISSN: 0020-0190</identifier><identifier>EISSN: 1872-6119</identifier><identifier>DOI: 10.1016/S0020-0190(00)00075-2</identifier><identifier>CODEN: IFPLAT</identifier><language>eng</language><publisher>Amsterdam: Elsevier B.V</publisher><subject>Algorithmics. Computability. Computer arithmetics ; Applied sciences ; Automata. Abstract machines. Turing machines ; Computer science; control theory; systems ; Decidability of emptiness ; Exact sciences and technology ; Real-time systems ; Theoretical computing ; Timed automata</subject><ispartof>Information processing letters, 2000-07, Vol.75 (1), p.1-7</ispartof><rights>2000 Elsevier Science B.V.</rights><rights>2000 INIST-CNRS</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c367t-eab9927ab5efbfcc9f3a27b10c5a79e11622adb0408d9d25a6794445718ed2a83</citedby><cites>FETCH-LOGICAL-c367t-eab9927ab5efbfcc9f3a27b10c5a79e11622adb0408d9d25a6794445718ed2a83</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.sciencedirect.com/science/article/pii/S0020019000000752$$EHTML$$P50$$Gelsevier$$H</linktohtml><link.rule.ids>314,776,780,3416,3551,27901,27902,45948,45978</link.rule.ids><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&amp;idt=1458684$$DView record in Pascal Francis$$Hfree_for_read</backlink></links><search><creatorcontrib>Bérard, Béatrice</creatorcontrib><creatorcontrib>Dufourd, Catherine</creatorcontrib><title>Timed automata and additive clock constraints</title><title>Information processing letters</title><description>The subclass of linear hybrid automata which consists of time automata extended with additive clock constraints is investigated. A model is proved to be strictly more expressive than the basic one and the test for emptiness becomes undecidable. Results are extended to timed automata with only four clocks and a restricted form of additive constraints.</description><subject>Algorithmics. Computability. Computer arithmetics</subject><subject>Applied sciences</subject><subject>Automata. Abstract machines. Turing machines</subject><subject>Computer science; control theory; systems</subject><subject>Decidability of emptiness</subject><subject>Exact sciences and technology</subject><subject>Real-time systems</subject><subject>Theoretical computing</subject><subject>Timed automata</subject><issn>0020-0190</issn><issn>1872-6119</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2000</creationdate><recordtype>article</recordtype><recordid>eNqFkM1LAzEQxYMoWKt_grAHET2sTrIf2ZxEil9Q8GA9h9lkFqLb3ZqkBf97Uyt6FAaGgd-bx3uMnXK44sDr6xcAATlwBRcAlwAgq1zssQlvpMhrztU-m_wih-wohLcE1WUhJyxfuCXZDNdxXGLEDId0WOui21Bm-tG8Z2YcQvTohhiO2UGHfaCTnz1lr_d3i9ljPn9-eJrdznNT1DLmhK1SQmJbUdd2xqiuQCFbDqZCqYjzWgi0LZTQWGVFhbVUZVlWkjdkBTbFlJ3v_q78-LGmEPXSBUN9jwON66CFlJInPIHVDjR-DMFTp1feLdF_ag56W47-Lkdvk2vYTipHi6Q7-zHAYLDvPA7GhT9xWTV1UybsZodRCrtx5HUwjgZD1nkyUdvR_WP0BYX-d24</recordid><startdate>20000731</startdate><enddate>20000731</enddate><creator>Bérard, Béatrice</creator><creator>Dufourd, Catherine</creator><general>Elsevier B.V</general><general>Elsevier Science</general><scope>IQODW</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>20000731</creationdate><title>Timed automata and additive clock constraints</title><author>Bérard, Béatrice ; Dufourd, Catherine</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c367t-eab9927ab5efbfcc9f3a27b10c5a79e11622adb0408d9d25a6794445718ed2a83</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2000</creationdate><topic>Algorithmics. Computability. Computer arithmetics</topic><topic>Applied sciences</topic><topic>Automata. Abstract machines. Turing machines</topic><topic>Computer science; control theory; systems</topic><topic>Decidability of emptiness</topic><topic>Exact sciences and technology</topic><topic>Real-time systems</topic><topic>Theoretical computing</topic><topic>Timed automata</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Bérard, Béatrice</creatorcontrib><creatorcontrib>Dufourd, Catherine</creatorcontrib><collection>Pascal-Francis</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Information processing letters</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Bérard, Béatrice</au><au>Dufourd, Catherine</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Timed automata and additive clock constraints</atitle><jtitle>Information processing letters</jtitle><date>2000-07-31</date><risdate>2000</risdate><volume>75</volume><issue>1</issue><spage>1</spage><epage>7</epage><pages>1-7</pages><issn>0020-0190</issn><eissn>1872-6119</eissn><coden>IFPLAT</coden><abstract>The subclass of linear hybrid automata which consists of time automata extended with additive clock constraints is investigated. A model is proved to be strictly more expressive than the basic one and the test for emptiness becomes undecidable. Results are extended to timed automata with only four clocks and a restricted form of additive constraints.</abstract><cop>Amsterdam</cop><pub>Elsevier B.V</pub><doi>10.1016/S0020-0190(00)00075-2</doi><tpages>7</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0020-0190
ispartof Information processing letters, 2000-07, Vol.75 (1), p.1-7
issn 0020-0190
1872-6119
language eng
recordid cdi_proquest_miscellaneous_27771571
source ScienceDirect Freedom Collection; Backfile Package - Computer Science (Legacy) [YCS]; Backfile Package - Mathematics (Legacy) [YMT]
subjects Algorithmics. Computability. Computer arithmetics
Applied sciences
Automata. Abstract machines. Turing machines
Computer science
control theory
systems
Decidability of emptiness
Exact sciences and technology
Real-time systems
Theoretical computing
Timed automata
title Timed automata and additive clock constraints
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-02-03T02%3A53%3A25IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Timed%20automata%20and%20additive%20clock%20constraints&rft.jtitle=Information%20processing%20letters&rft.au=B%C3%A9rard,%20B%C3%A9atrice&rft.date=2000-07-31&rft.volume=75&rft.issue=1&rft.spage=1&rft.epage=7&rft.pages=1-7&rft.issn=0020-0190&rft.eissn=1872-6119&rft.coden=IFPLAT&rft_id=info:doi/10.1016/S0020-0190(00)00075-2&rft_dat=%3Cproquest_cross%3E27771571%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c367t-eab9927ab5efbfcc9f3a27b10c5a79e11622adb0408d9d25a6794445718ed2a83%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=27771571&rft_id=info:pmid/&rfr_iscdi=true