School of Mathematics and Statistics - Research Publications

Permanent URI for this collection

Search Results

Now showing 1 - 3 of 3
  • Item
    Thumbnail Image
    A Study of Aggregated Speed in Road Networks Using Cellular Automata
    ZHANG, L ; Shiri, S ; Garoni, T ; Was, J ; Sirakoulis, GC ; Bandini, S (Springer, 2014)
    Several recent works have focused on studying the relationship between the aggregated flow and density in arterial road networks. Analogous studies involving aggregated speed appear not to have been yet undertaken, however. Here we study and compare such relations for arterial road networks controlled by different types of adaptive traffic signal systems, under various boundary conditions. To study such systems we simulate stochastic cellular automaton models. Our simulation results suggest that network speed could be used as a surrogate for density, due to a strong anticorrelation between these two network observables. Since speed estimates can be more easily obtained than density estimates, e.g. from probe vehicle data, this suggests that Macroscopic Fundamental Diagrams relating aggregated flow with speed might be a practically useful alternative to those relating flow to density.
  • Item
    Thumbnail Image
    TURING MACHINES TO WORD PROBLEMS
    Miller, CF ; Downey, R (CAMBRIDGE UNIV PRESS, 2014-01-01)
  • Item
    No Preview Available
    Bounding Embeddings of VC Classes into Maximum Classes
    Rubinstein, JH ; RUBINSTEIN, B ; Bartlett, PL ; Vovk, V ; Papadopoulos, H ; Gammerman, A (Springer, 2015)
    One of the earliest conjectures in computational learning theory-the Sample Compression conjecture-asserts that concept classes (equivalently set systems) admit compression schemes of size linear in their VC dimension. To-date this statement is known to be true for maximum classes---those that possess maximum cardinality for their VC dimension. The most promising approach to positively resolving the conjecture is by embedding general VC classes into maximum classes without super-linear increase to their VC dimensions, as such embeddings would extend the known compression schemes to all VC classes. We show that maximum classes can be characterised by a local-connectivity property of the graph obtained by viewing the class as a cubical complex. This geometric characterisation of maximum VC classes is applied to prove a negative embedding result which demonstrates VC-d classes that cannot be embedded in any maximum class of VC dimension lower than 2d. On the other hand, we show that every VC-d class C embeds in a VC-(d+D) maximum class where D is the deficiency of C, i.e., the difference between the cardinalities of a maximum VC-d class and of C. For VC-2 classes in binary n-cubes for 4 <= n <= 6, we give best possible results on embedding into maximum classes. For some special classes of Boolean functions, relationships with maximum classes are investigated. Finally we give a general recursive procedure for embedding VC-d classes into VC-(d+k) maximum classes for smallest k.