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
<?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>