Name
Abstract | ||
|---|---|---|
Reversible computational models with discrete internal states are said to be time-symmetric, if they can go back and forth in time by applying the same transition function. The direction in time is adjusted by a weak transformation of the phase-space, that is, an involution. So, these machines themselves cannot distinguish whether they run forward or backward in time. From this viewpoint, finite state machines and pushdown machines are studied in detail. In essence, it turns out that there are reversible machines which are not time-symmetric, but equivalent time-symmetric machines can effectively be constructed. The notion of time-symmetry is discussed, several examples are given, and further results concerning unary inputs and descriptional complexity issues are shown. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-642-38986-3_14 | RC |
Keywords | Field | DocType |
finite state machine,transition function,discrete internal state,descriptional complexity issue,equivalent time-symmetric machine,reversible machine,weak transformation,time-symmetric machine,pushdown machine,reversible computational model,unary input | Cellular automaton,Discrete mathematics,Unary operation,Computer science,Theoretical computer science,Finite-state machine,Computational model,Turing machine,Regular language,Transition function | Conference |
Citations | PageRank | References |
0 | 0.34 | 26 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Martin Kutrib | 1 | 778 | 89.77 |
| Thomas Worsch | 2 | 150 | 36.77 |