Automatically assigned DDC number: 00433

Manually assigned DDC number: 00433

Number of references: 4

Title: Back to the Future: Towards a Theory of Timed Regular Languages

Author:

Author:

Subject: Rajeev Alur,Thomas A. Henzinger Back to the Future: Towards a Theory of Timed Regular Languages

Description: : Timed automata are finite-state machines constrained by timing requirements so that they accept timed words --- words in which every symbol is labeled with a real-valued time. These automata were designed to lead to a theory of finite-state real-time properties with applications to the automatic verification of real-time systems. However, both deterministic and nondeterministic versions suffer from drawbacks: several key problems, such as language inclusion, are undecidable for nondeterministic timed automata, whereas deterministic timed automata lack considerable expressive power when compared to decidable real-time logics. This is why we introduce two-way timed automata --- timed automata that can move back and forth while reading a timed word. Two-wayness in its unrestricted form leads, like nondeterminism, to the undecidability of language inclusion. However, if we restrict the number of times an input symbol may be revisited, then two-wayness is both harmless and desirable. We s...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1997-06-17

Pubyear: 1992

Format: ps

Identifier: http://citeseer.ist.psu.edu/149673.html

Source: http://www.cis.upenn.edu/~alur/Focs92.ps.gz

Language: en

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

<?xml   version="1.0"   encoding="UTF-8"?>

<references_metadata>

      <rec   ID="/64835.html"   Type="inproceedings"   CiteSeer_Book="Symposium   on   Principles   of   Distributed   Computing"   CiteSeer_Volume=""   Title="The   Benefits   of   Relaxing   Punctuality,">

            <identifier   Org="ISBN:0387569227"   Paper_ID="/64835.html"   Extracted="0387569227"   DDC="511.3/0285"   Normalized_DDC="51130285"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:0897914392"   Paper_ID="/64835.html"   Extracted="0897914392"   DDC="004.36"   Normalized_DDC="00436"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540004009"   Paper_ID="/64835.html"   Extracted="3540004009"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:354022940X"   Paper_ID="/64835.html"   Extracted="354022940X"   DDC="004.35"   Normalized_DDC="00435"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540230688"   Paper_ID="/64835.html"   Extracted="3540230688"   DDC="004/.33"   Normalized_DDC="00433"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540253041"   Paper_ID="/64835.html"   Extracted="3540253041"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540440437"   Paper_ID="/64835.html"   Extracted="3540440437"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540555641"   Paper_ID="/64835.html"   Extracted="3540555641"   DDC="005.1/1"   Normalized_DDC="00511"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540575294"   Paper_ID="/64835.html"   Extracted="3540575294"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540600434"   Paper_ID="/64835.html"   Extracted="3540600434"   DDC="005.1/01/512"   Normalized_DDC="005101512"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:354062600X"   Paper_ID="/64835.html"   Extracted="354062600X"   DDC="004.1/9"   Normalized_DDC="00419"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540648968"   Paper_ID="/64835.html"   Extracted="3540648968"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540662022"   Paper_ID="/64835.html"   Extracted="3540662022"   DDC="004.24"   Normalized_DDC="00424"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540665366"   Paper_ID="/64835.html"   Extracted="3540665366"   DDC="004/.01/5113"   Normalized_DDC="004015113"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540672591"   Paper_ID="/64835.html"   Extracted="3540672591"   DDC="004.1/9"   Normalized_DDC="00419"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540709517"   Paper_ID="/64835.html"   Extracted="3540709517"   />

            <identifier   Org="ISBN:3540733671"   Paper_ID="/64835.html"   Extracted="3540733671"   />

            <identifier   Org="ISBN:3540744061"   Paper_ID="/64835.html"   Extracted="3540744061"   />

            <identifier   Org="ISBN:3540754539"   Paper_ID="/64835.html"   Extracted="3540754539"   DDC="005.3"   Normalized_DDC="0053"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540766480"   Paper_ID="/64835.html"   Extracted="3540766480"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.058823529411764705"   />

      </rec>

      <rec   ID="/17094.html"   Type="inproceedings"   CiteSeer_Book="IEEE   Symposium   on   Foundations   of   Computer   Science"   CiteSeer_Volume=""   Title="A   Really   Temporal   Logic,">

            <identifier   Org="ISBN:0471184063"   Paper_ID="/17094.html"   Extracted="0471184063"   DDC="658.4038"   Normalized_DDC="6584038"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:078032563X"   Paper_ID="/17094.html"   Extracted="078032563X"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:0792361490"   Paper_ID="/17094.html"   Extracted="0792361490"   DDC="005.1/01/5113"   Normalized_DDC="0051015113"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:0818619821"   Paper_ID="/17094.html"   Extracted="0818619821"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:0818627352"   Paper_ID="/17094.html"   Extracted="0818627352"   DDC="004/.01/5113"   Normalized_DDC="004015113"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:1558604804"   Paper_ID="/17094.html"   Extracted="1558604804"   />

            <identifier   Org="ISBN:1586035762"   Paper_ID="/17094.html"   Extracted="1586035762"   />

            <identifier   Org="ISBN:3540205365"   Paper_ID="/17094.html"   Extracted="3540205365"   DDC="005.13"   Normalized_DDC="00513"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540440437"   Paper_ID="/17094.html"   Extracted="3540440437"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540552103"   Paper_ID="/17094.html"   Extracted="3540552103"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540555641"   Paper_ID="/17094.html"   Extracted="3540555641"   DDC="005.1/1"   Normalized_DDC="00511"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540564969"   Paper_ID="/17094.html"   Extracted="3540564969"   DDC="511.3/0285"   Normalized_DDC="51130285"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540566627"   Paper_ID="/17094.html"   Extracted="3540566627"   DDC="005.13/1"   Normalized_DDC="005131"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540575294"   Paper_ID="/17094.html"   Extracted="3540575294"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:354062600X"   Paper_ID="/17094.html"   Extracted="354062600X"   DDC="004.1/9"   Normalized_DDC="00419"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540627812"   Paper_ID="/17094.html"   Extracted="3540627812"   DDC="005.1/2"   Normalized_DDC="00512"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540627901"   Paper_ID="/17094.html"   Extracted="3540627901"   DDC="004.2/1"   Normalized_DDC="00421"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540638881"   Paper_ID="/17094.html"   Extracted="3540638881"   DDC="005.1/01/512"   Normalized_DDC="005101512"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540727329"   Paper_ID="/17094.html"   Extracted="3540727329"   />

            <identifier   Org="ISBN:3540744061"   Paper_ID="/17094.html"   Extracted="3540744061"   />

      </rec>

      <rec   ID="/110303.html"   Type="inproceedings"   CiteSeer_Book="Conference   Record   of   the   Eighteenth   Annual   ACM   Symposium   on   Principles   of   Programming   Languages"   CiteSeer_Volume=""   Title="Temporal   Proof   Methodologies   for   Real-time   Systems,">

            <identifier   Org="ISBN:0471139467"   Paper_ID="/110303.html"   Extracted="0471139467"   DDC="621.3/03"   Normalized_DDC="621303"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:0780309111"   Paper_ID="/110303.html"   Extracted="0780309111"   DDC="620.82"   Normalized_DDC="62082"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:0818627352"   Paper_ID="/110303.html"   Extracted="0818627352"   DDC="004/.01/5113"   Normalized_DDC="004015113"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:0818627603"   Paper_ID="/110303.html"   Extracted="0818627603"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:0818680679"   Paper_ID="/110303.html"   Extracted="0818680679"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540000291"   Paper_ID="/110303.html"   Extracted="3540000291"   DDC="004/.01/51"   Normalized_DDC="0040151"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540550925"   Paper_ID="/110303.html"   Extracted="3540550925"   DDC="004/.33"   Normalized_DDC="00433"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540555641"   Paper_ID="/110303.html"   Extracted="3540555641"   DDC="005.1/1"   Normalized_DDC="00511"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540558225"   Paper_ID="/110303.html"   Extracted="3540558225"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540563202"   Paper_ID="/110303.html"   Extracted="3540563202"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540572090"   Paper_ID="/110303.html"   Extracted="3540572090"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:354058241X"   Paper_ID="/110303.html"   Extracted="354058241X"   DDC="511.3"   Normalized_DDC="5113"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540584684"   Paper_ID="/110303.html"   Extracted="3540584684"   DDC="004/.33"   Normalized_DDC="00433"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540588671"   Paper_ID="/110303.html"   Extracted="3540588671"   DDC="670.42/7"   Normalized_DDC="670427"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540630104"   Paper_ID="/110303.html"   Extracted="3540630104"   DDC="005.2/73"   Normalized_DDC="005273"   Normalized_Weight="0.06666666666666667"   />

      </rec>

      <rec   ID="/522428.html"   Type="article"   CiteSeer_Book="Acta   Informatica"   CiteSeer_Volume="30"   Title="From   {ATP}   to   Timed   Graphs   and   Hybrid   Systems,">

            <identifier   Org="ISBN:0387569227"   Paper_ID="/522428.html"   Extracted="0387569227"   DDC="511.3/0285"   Normalized_DDC="51130285"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:081864480X"   Paper_ID="/522428.html"   Extracted="081864480X"   DDC="004/.33"   Normalized_DDC="00433"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540555641"   Paper_ID="/522428.html"   Extracted="3540555641"   DDC="005.1/1"   Normalized_DDC="00511"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540558225"   Paper_ID="/522428.html"   Extracted="3540558225"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540563202"   Paper_ID="/522428.html"   Extracted="3540563202"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540573186"   Paper_ID="/522428.html"   Extracted="3540573186"   DDC="004.1/9"   Normalized_DDC="00419"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540578803"   Paper_ID="/522428.html"   Extracted="3540578803"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540580271"   Paper_ID="/522428.html"   Extracted="3540580271"   DDC="005.13/1"   Normalized_DDC="005131"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540581790"   Paper_ID="/522428.html"   Extracted="3540581790"   DDC="004.2/4/015113"   Normalized_DDC="00424015113"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540583297"   Paper_ID="/522428.html"   Extracted="3540583297"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540584684"   Paper_ID="/522428.html"   Extracted="3540584684"   DDC="004/.33"   Normalized_DDC="00433"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540587152"   Paper_ID="/522428.html"   Extracted="3540587152"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540604723"   Paper_ID="/522428.html"   Extracted="3540604723"   DDC="629.8/9"   Normalized_DDC="62989"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:354061155X"   Paper_ID="/522428.html"   Extracted="354061155X"   DDC="629.8/9"   Normalized_DDC="62989"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540616047"   Paper_ID="/522428.html"   Extracted="3540616047"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540616489"   Paper_ID="/522428.html"   Extracted="3540616489"   DDC="004/.33"   Normalized_DDC="00433"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540630104"   Paper_ID="/522428.html"   Extracted="3540630104"   DDC="005.2/73"   Normalized_DDC="005273"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540650032"   Paper_ID="/522428.html"   Extracted="3540650032"   DDC="004/.33"   Normalized_DDC="00433"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540651934"   Paper_ID="/522428.html"   Extracted="3540651934"   DDC="004.16"   Normalized_DDC="00416"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540699260"   Paper_ID="/522428.html"   Extracted="3540699260"   />

      </rec>

      <rec   ID="SELF"   Type="SELF"   CiteSeer_Book="SELF"   CiteSeer_Volume="SELF"   Title="Back   to   the   Future:   Towards   a   Theory   of   Timed   Regular   Languages">

            <identifier   Org="ISBN:0471184063"   Paper_ID="SELF"   Extracted="0471184063"   DDC="658.4038"   Normalized_DDC="6584038"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:0897915917"   Paper_ID="SELF"   Extracted="0897915917"   />

            <identifier   Org="ISBN:1600219977"   Paper_ID="SELF"   Extracted="1600219977"   DDC="629.8/92"   Normalized_DDC="629892"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540230688"   Paper_ID="SELF"   Extracted="3540230688"   DDC="004/.33"   Normalized_DDC="00433"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540240586"   Paper_ID="SELF"   Extracted="3540240586"   DDC="005.3"   Normalized_DDC="0053"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540251081"   Paper_ID="SELF"   Extracted="3540251081"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540304959"   Paper_ID="SELF"   Extracted="3540304959"   DDC="005.3"   Normalized_DDC="0053"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540309462"   Paper_ID="SELF"   Extracted="3540309462"   DDC="003/.3"   Normalized_DDC="0033"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540581790"   Paper_ID="SELF"   Extracted="3540581790"   DDC="004.2/4/015113"   Normalized_DDC="00424015113"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540584684"   Paper_ID="SELF"   Extracted="3540584684"   DDC="004/.33"   Normalized_DDC="00433"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540609229"   Paper_ID="SELF"   Extracted="3540609229"   DDC="004/.01/511"   Normalized_DDC="00401511"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540616489"   Paper_ID="SELF"   Extracted="3540616489"   DDC="004/.33"   Normalized_DDC="00433"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540626166"   Paper_ID="SELF"   Extracted="3540626166"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540647813"   Paper_ID="SELF"   Extracted="3540647813"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540648968"   Paper_ID="SELF"   Extracted="3540648968"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540662243"   Paper_ID="SELF"   Extracted="3540662243"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.06666666666666667"   />

      </rec>

</references_metadata>

www.000webhost.com