Name
Title | ||
|---|---|---|
On timed automata with discrete time – structural and language theoretical characterization |
Abstract | ||
|---|---|---|
We develop a structural and language theoretical characterization of timed languages over discrete time in terms of a variant of Büchi automata and languages. The so-called tick automaton is a standard Büchi automaton with a special “clock-tick”-input symbol modeling the discrete flow of time. Based on these characterizations we give an alternative proof for the fact that the class of regular timed languages is closed under complementation and formulate a time-warp lemma which, similar to a pumping lemma, can be used to show that a timed language is not regular. The characterizations hold alike for timed automata with and without periodic clock constraints. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11505877_24 | Developments in Language Theory |
Keywords | Field | DocType |
so-called tick automaton,standard b,periodic clock constraint,language theoretical characterization,input symbol,time-warp lemma,discrete time,chi automaton,alternative proof,discrete flow | Discrete mathematics,Context-free language,Nondeterministic finite automaton,Algebra,Computer science,Automaton,Algorithm,Timed automaton,Pumping lemma for regular languages,Regular language,Lemma (mathematics),Büchi automaton | Conference |
Volume | ISSN | ISBN |
3572 | 0302-9743 | 3-540-26546-5 |
Citations | PageRank | References |
1 | 0.35 | 9 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hermann Gruber | 1 | 185 | 13.28 |
| Markus Holzer | 2 | 138 | 12.30 |
| A. Kiehn | 3 | 249 | 22.96 |
| Barbara König | 4 | 130 | 12.58 |