Synchronous Remote Rendering for VR

Remote rendering for VR is a technology that enables high-quality VR on low-powered devices. This is realized by offloading heavy computation and rendering to high-powered servers that stream VR as video to the clients. This article focuses on one specific issue in remote rendering when imperfect frame timing between client and server may cause recurring frame drops. We propose a system design that executes synchronously and eliminates the aforementioned problem. The design is presented, and an implementation is tested using various networks and hardware. The design cannot drop frames due to synchronization issues but may on the other hand stall if temporal disturbances occur, e.g., due to network delay spikes or loss. However, experiments confirm that such events can remain rare given an appropriate environment. For example, remote rendering on an intranet at 90 fps with a server located approximately 50 km away yielded just 0.002% stalled frames while rendering with extra latency corresponding to the duration of exactly one frame (11.1ms at 90 fps). In a LAN without extra latency setting, i.e., with latency equal to locally rendered VR, 0.009% stalls were observed while using a wired Ethernet connection and 0.058% stalls when using 5GHz wireless IEEE 802.11 ac.

Introduction
With increasing interest in virtual reality (VR) comes an opportunity to deploy VR functionality in phones or other thin devices that, due to cost or mobility, lack the computational power required to render high-quality VR on their own hardware [1]. By offloading game-logic and rendering to strong servers in the local network or at the edge, and streaming the live-rendered content as video, these thin devices would merely need strong hardware decoders and network connections to enable high quality VR. In the end, this can reduce the cost and increase the mobility of VR clients.
There are several categories of remote rendering for VR already available in the present market. On the inexpensive low end, there are apps designed to stream VR from home PCs to phones or other thin devices [2][3][4]. When a phone is used as client, it is placed in a VR gadget that can be used as Head-Mounted Display (HMD) by having the phone act as display [5][6][7]. This enables an inexpensive alternative of VR for users who already have high-powered PCs at home but no high-end headsets. On the high end of concurrent remote VR, there are for example the wireless VR adapters available to HTC Vive and Oculus Rift [8,9] and USBtethered remote rendering for Oculus Quest [10]. In this work, we present an architecture that can be used to minimize both latency and the amount of frame drops in remote rendering systems for VR.
In remote rendering, the latency from input to perceived effect on-screen must generally be low in order to provide a decent user experience. A popular application of remote rendering is cloud gaming. The latency requirements of cloud gaming depend on the type of game, but typically range between 60 and 120 ms [11]. With VR, however, this budget is defined as the Motion-To-Photon (MTP) budget and expected to range between 7 ms [12][13][14] and 20 ms [11,[15][16][17][18]. The 7 ms deadline was recently (2019) reached with Valve's VR headset Index, which has a 144 Hz mode (6.94 ms budget). However, note that there may be additional delays other than the refresh interval (e.g., from input devices), while the latter is the lowest possible latency on the display in question. For example, framerates of up to 1800 Hz are expected to be required for a life-like experience, but a latency of 7 ms would still be unnoticeable on such displays according to previous research [19].
1.1. VR Remote Rendering. A multitude of steps are required for each frame to enable the remote rendering of VR: (1) Client: get input data from input devices (2) Client: send the input data to the server Two of the most common VR headsets are the HTC Vive and Oculus Rift, both still in the top five of most common VR headsets on Steam as of September 2020 [20]. Both these HMDs use a 90 Hz refresh rate, which results in a frame time budget of 11.1 ms. However, even though the MTP-budget may be 20 ms, this does not mean that we obtain an additional 8.9 ms headroom that can be allocated to network latency. The MTP depends on the VR system in question, partly the devices and drivers that continuously provide the rotation and translation data of the headset. For example, in the HTC Vive, the rotation of the HMD is updated at 1000 Hz [21,22], thus adding at least 1 ms to the MTP delay in the worst case. On the other hand, the Oculus Rift also samples tracking data at 1000 Hz, but sends two updates with each packet on the USB cable, resulting in a 500 Hz update rate or 2 ms worst-case delay [23]. Worse yet, supposedly, the update rate for translations may for example be as low as 250 Hz on the HTC Vive [21]. Additionally, there is the added latency caused by drivers, display, and scan-out. Scanning out the image from GPU to display requires a significant amount of time, typically one full frame time [24]. Thus, even on locally rendered VR, there is a significant amount of latency. However, by predicting future motions [25,26] and utilizing other latency-mitigating technologies such as 2D- [26][27][28][29] and 3D-image warping [30][31][32], both these systems can achieve near-zero latency from the user perspective ( [33], Chapter~12). Although the mentioned mitigation strategies can severely reduce the rotation and translation latency, it is always better to avoid a problem than to mitigate it [27]. Furthermore, interaction latency remains difficult to mitigate without moving the interactive component to the client [34], which complicates development and may defeat the purpose of using remote rendering.
1.1.1. Local Latency Mode. Ideally, the remote rendering solution completes all previously mentioned steps (1)(2)(3)(4)(5)(6)(7)(8) and is able to present a new frame before the Vertical Synchronization (VSync) deadline for the display is hit (VSync is a technique that ensures that a new scan-out does not begin until the previous has finished. VSync avoids an issue where the new frame may overwrite parts of the old frame, commonly referred to as tearing [24]). If the solution achieves this, the VR experience has the potential to be no different in terms of latency to locally rendered VR, which we refer to as local latency mode. Naturally, this is difficult to achieve because the game logic and rendering itself may already consume most of the available frame time. Adding encoding, transmission and decoding may break the deadline in demanding games when using common codecs such as H.264, thus introducing delays or lowering the framerate.

Server-Client Synchronization Challenges.
A naive remote rendering solution without special hardware typically consists of a server and client that execute in parallel without any synchronization. The server runs a game independently and is continuously fed input data which is used to render the following frame. The rendered frame is sent to the client that runs its own independent game loop and continuously presents its most recently received frame. Such a design causes issues with frame timing between the two programs. Ideally, new frames are decoded and ready to be displayed on the client a few milliseconds before the VSync deadline. This is difficult to achieve without some synchronization that for example decides when the server should start rendering [22].

Synchronous Design Motivation.
We propose a remote VR solution that is synchronous and, in an ideal scenario, bufferless. In the latter case, it does not add latency and keeps the same MTP as if the HMD was used locally. However, due to the synchronization, it may reduce the framerate if the deadline of 11.1 ms (at 90 fps) cannot be met in the present environment (see Figure 1). In order to maintain the deadline though, the system may reduce the resolution of the images to reduce time consumption of the codec and other components. The prototype may also inject one frame delay to maintain 90 fps when local latency operation is not possible. When this is done, the system introduces latency that would not be present in local rendering and is thus no longer running in local latency mode.
In the proposed design, the remote rendering functionality is integrated into the game engine and acts as a part of the framerate budget. This restricts portability of the solution since it cannot run as a separate process, but must be written into the game. However, it enables a shorter MTP path because the rendering on the server waits for a new HMD pose before starting each frame. Likewise, the client waits for the resulting rendered images to be transmitted back from the server. The waiting ensures that the two stay in sync and 2 International Journal of Computer Games Technology that operation continues as soon as possible upon arrival of the required data. The design allows for local latency operation, will not suffer frame drops due to synchronization issues, and achieves minimal latency because each step in the chain begins as soon as possible. Furthermore, because server and client are in sync, every frame rendered at the server will be displayed on the client. This is because the server will not start rendering until it receives new input, and the client will not send input until it has presented the previous frame. Networkinduced frame drops due to packet loss cannot occur in this system. Frame stalls, on the other hand, will occur when the refresh interval deadline cannot be kept, for example, due to losses which may cause retransmissions. The display may in such cases show the same frame multiple times which may be experienced as a playback stall by the user. Note that the effect of a missed deadline is implementation-dependent though and not necessarily a frozen image if the VR client utilizes image warping techniques which may warp the last image for a new orientation [29].
Due to the guarantee of arrival of all frames (guaranteed by the application layer protocol, e.g., by reliable UDP or TCP), the system begins streaming with one I-frame and runs entirely on P-frames thereafter. This is not possible in an asynchronous system which must recover from losses by sending a new I-frame that does not reference any lost data. Data delivery is guaranteed in this work with an in-house implementation of reliable UDP [35] imposing strict control of the retransmission timeout. Finally, the delay that may be injected into the system is constant and always the length of one full frame, e.g., 11.1 ms at 90 fps. This may make it easier for future motion prediction algorithms to make accurate predictions when compared to variable or unknown latencies. In an asynchronous system, the delay may vary between zero and nearly a full frame time, which may reduce prediction accuracy.  (2) Reduced framerate: the system cannot finish within the deadline, and fps will thus be reduced to half. (3) Delay injection: one frame delay is injected into the system. It is initialized by sending an extra input packet after decoding which will trigger parallel processing of two frames from then on, both delayed by one frame. The white Sync-bar is implementation-dependent and in this case refers mainly to the time consumption of the function WaitGetPoses() in the OpenVR API [75], which will return "running start" milliseconds before the next VSync deadline, typically 2 ms [76].
3 International Journal of Computer Games Technology parameters and hardware. The research is meant not only to pave way for future work in the field of synchronous remote rendering for VR but also to produce knowledge that may be of use for related work in any remote rendering scenario. Our main contribution is the design and evaluation of the synchronous remote VR system. The remainder of this article is structured as follows: In Section 2, we discuss the state of the art of remote rendering for VR. Section 3 presents the design of the system and details of its implementation. Section 4 shows how the system performed in a number of tests with various networks and hardware. Finally, Section 5 summarizes the most important conclusions of the work, its limitations, and potential future work.

Related Work
Remote rendering consists of many subcategories and has been both available and studied extensively for decades. Some notable samples from history are presented in the following list with release dates in parenthesis. The list provides an introduction to the field but is however by no means complete. For a more comprehensive literature review, we refer to the following publications: a literature review regarding interactive remote rendering systems [1], a review on existing (in 2016) web-based visualization applications [36], a survey on mobile cloud computing [37], and a survey on platforms for interactive clusterbased multiscreen rendering [38].
(i) (1984) X Window [39] is one of the earliest examples of a remote renderer. It is a windowing system that by design consists of a server and client and therefore easily can be used remotely. X Window has been used extensively in research, for example, in [40], the authors found that applications that generate small datagrams when using X Window create severe overhead and may only utilize 25% of the maximum bandwidth. The authors suggest that updates should not be flushed unless necessary as this will generate smaller datagrams; updates should instead be buffered and sent in bulk when possible. The caveat of this is of course that it increases latency (ii) (1995) Virtual Network Computing (VNC) [41] is a protocol for remote access to graphical user interfaces that is independent of operating and windowing system. It has been described as an improvement over X Window [41]. The authors of [42] quantified the user experience while using VNC and found that a low latency network is the most important factor, more so than bandwidth (iii) (2000) OpenGL Vizserver [43] is a remote rendering system developed by Silicon Graphics Inc. that utilizes hardware acceleration with OpenGL. In [44], the authors used both VNC and OpenGL Vizserver to show how distributed teams can simultaneously view and steer simulations (iv) (2002) Paraview [45] is an open-source application that enables interactive remote visualization of datasets. It has been widely used in the scientific community and is targeted towards viewing extremely large datasets that can be rendered by supercomputers or server clusters. For example, one study used ParaView to provide insights into the evolution of the early universe [46]. The dataset used in that study consisted of several hundred time steps of point simulation data, with each time-step containing approximately two million point particles [46].
( OnLive was discontinued and sold to Sony in 2015 [49]. A study was conducted in 2011 that measured the latency of OnLive in comparison to StreamMyGame and found processing delays ranging between 110 and 221 ms in tests with OnLive and between 356 and 471 ms in tests with StreamMyGame [50]. The processing delay was described as the difference between player input and presentation of a corresponding frame [50], i.e., MTP (viii) (2014) GamingAnywhere [51] is an open source cloud gaming system published in 2014. The publication of GamingAnywhere included performance comparisons with the OnLive system and showed significant improvement [51]. Another study that involved both OnLive and GamingAnywhere found that the player performance decreases by 25% with each 100 milliseconds of latency when using these services [52] (  [60]. CloudXR is in a closed beta at the time of writing (spring 2021).
In the following subsections, we will go into more details surrounding remote rendering for VR and review relevant publications in the field.

360°Panorama VR.
Remote rendering for VR has been studied for some time. Most solutions involve rendering to a panorama that covers every angle; this technique is used in 360°videos and has been widely used in the research community, commonly in conjunction with the game engine unity [61][62][63][64]. In [64], authors studied remote rendering of 360°VR by using two laptops and reported an end-to-end latency of 30 ms with a bitrate of 30 Mbps for a stereo 1080p resolution at 30 fps. The rendered panorama was split into slices, and only the ones deemed necessary depending on the current view-direction were transmitted; this reduced the bitrate by around 50%. A similar study was conducted where focus lied on bandwidth savings by only streaming the field of view (FoV) of the panorama image [63]. The authors of that study were able to stream 8 K 360-VR through a 4G network from a PC to a Gear VR phone and saved more than 80% bandwidth compared to sending the entire panorama. The term motion-to-update [63] was introduced and reported to range between 67.4 and 559.6 ms depending on resolution, network, and codec. Our understanding is that the motion-to-update is used here to more accurately describe the MTP of 360-VR due to considering server updates. In [61], authors studied bandwidth reduction further and found that by storing rendered images on the server and reusing them for clients with similar positions and view directions, a 90% reduction in server computation burden and 95% reduction in bitrate could be achieved. Finally, foveated streaming of 360°videos was studied in [62]. Bandwidth was not addressed in that work though; the aim was instead to reduce cognitive load and visual discomfort.
By using a panorama, new viewports caused by rotations of the headset can instantly be rendered by selecting a different part of the already acquired panorama image. This makes panoramas ideal for video in which just three degrees of freedom are used (3-DOF), i.e., rotations around the X-, Y-, and Z-axis. However, panoramas require more memory and more time to render, which makes them difficult to use with high framerates in real-time. To create a 360°view live, one may render a cube-map, which requires six cameras and therefore six rendering passes [64][65][66]. While some culling can be done in this process [65], cube map rendering can never be as efficient as rendering just the viewport. They are furthermore not efficient for 6-DOF (with additional translations along X, Y, and Z) and/or interactive scenes. When the content of the scene changes due to user interaction or by other events that occur in the scene, a new image showing the change must be downloaded unless it can be rendered on the client. Due to these issues, we render just the default viewport for where the user is currently looking, which is a common approach in low-latency implementations and no different from local VR in terms of rendered pixels.

Split
Rendering. There are also split-or collaborativerendering solutions [34,65,67]. By rendering the most time-sensitive or low-fidelity objects on the client and more demanding ones at the server, one may maintain both responsiveness and visual quality. This technique has been applied to remote rendering for VR, for instance, with the 5 International Journal of Computer Games Technology background consisting of panorama images prerendered at the server at every position in the game along a spaced grid [34]. Another approach renders a cube map live as background at the server while interactive objects are rendered on the client [65].
While split-rendering solutions can achieve low latency for interactive components even in poor network conditions, we question if they may be too complex and difficult to scale for industry development. The inherent issue of splitrendering is that developers must be concerned with developing an end-user application that consists of both a server and client part, which implies additional costs. Though less critical, there is also the added hassle for the customer that must download and keep updated the unique client executable for each game. Additionally, the point of remote rendering is to achieve high quality visuals on low-powered devices; therefore, it is not ideal to render any object on the client as the visual quality of any such object will be limited to what the low-powered device can output. However, judging by current talks in the industry, we note that there seems to be a push towards split rendering and a belief that this will solve the current generation of remote VR [68]. Still, some are sceptical [69], and only time will tell which technologies will be accepted by the market. We expect that split rendering may be a compromise to make remote VR work on present-day hardware, but it is hardly the ultimate solution for future generations.
With the design proposed in this article, the client can be seen as a video player that may run any game that the server provides. The server process is unique per game though as remote rendering functionality must be added to the game engine and does not run as a separate process.
2.3. Nonpanoramic VR. Not using a panorama saves time and bandwidth, but it also puts immense requirements of low latency and stability on the VR system. A new image must be downloaded at a rate equal to the refresh-rate of the HMD. And if this cannot be achieved on time, the VR experience may be ruined. Building such a system can be approached easiest by having an external process copy the rendered images of the VR game, encode them, and send them across the network for decoding on the client. The pros of this approach are that it is simple and that the remote functionality can be added to any existing game without modification, because it is essentially a screen recorder. It may be difficult to optimize such a general process though, especially ensuring an optimal frame synchronization.

Screen-Recorder
Approach. The authors of [70] built a short-range (LAN) remote rendering VR system with commodity hardware. Their system is able to capture images from Steam VR games, encode them with JPEG using a GTX Titan X GPU, and transmit them across a WiGig network. To measure the latency as perceived by the user, they record two HMDs side-by-side with a 240 fps camera, one of which contains the local VR rendering, and the other the remote. By comparing the difference of the HMD images, they conclude that the added latency is in the range of 12 ± 2 ms. The presented solution is a typical example of a screen-recorder approach where remote rendering functionality can be added to any existing game since it is an external process. This approach is economical and easy to bring to the market but also difficult to optimize since there is no lowlevel control of the game, as is revealed in the latency.

Game
Integration and VSync Estimation. In [22], authors report on another short-range remote rendering VR system that also utilizes a WiGig connection but is integrated into the game. Encoding is done by using the Nvidia Video Codec SDK [71], H.264, and a GTX Titan X. They utilize four parallel encoder threads as well as four parallel decoders. They save time by starting the encoding of the first eye immediately after its rendering is complete. This means that the encoding of the first eye is done in parallel with the rendering of the second. Furthermore, the authors of the work propose a technique that involves estimating when the server should optimally start rendering in order to minimize the risk of missing the VSync deadline on the client. Unless some form of synchronization is applied, the waiting time on the client to the next VSync signal will drift every frame until a frame is missed in a repetitive pattern [22]. According to their experiments, the VSync estimation results in missing between 0.1 and 0.2% of all deadlines, which is on average one frame drop every 5-11 seconds at 90 fps. This is a significant improvement over a naive implementation though, between 5.3 and 14.3% of frames were dropped without the synchronization estimation. Finally, an end-to-end latency of 16 ms in software is reported; our understanding is that this is the average of the most demanding scene. In our work, we use a similar approach but utilize the proposed synchronous design which solves the synchronization problem completely.

2.3.3.
Example from Industry. The synchronization issue and time drift can also be observed in a developer blog from the creators of VRidge [72]. They show how their previous implementation caused time drift and how an update mitigates the issue. Although less recurrent after the update, the problem seems not entirely solved as frames are still occasionally dropped also in the improved version. There are no exact numbers reported, but judging from the graph in [72], it seems around 0.3% of frames are still dropped in the updated version.

Measurements.
Measuring the performance of a remote rendering system is difficult if it operates asynchronously. For example, if image quality should be measured, one may save every rendered frame on the server and client and compare them by using an objective image quality estimator after the streaming session has ended. Saving every frame to disk, for example, may reduce performance though and may therefore increase the number of missed frames on the client, causing invalid measurement results. A method for addressing this issue is known as slow-motion benchmarking and was applied and studied with a number of thin clients including VNC [73]. Slow-motion benchmarking is an inherent feature of the proposed synchronous architecture which will slow down and utilize retransmissions if needed to deliver to 6 International Journal of Computer Games Technology the client all frames rendered by the server. There are therefore no lost frames, which makes image quality estimation simple. The delta-time of the server can also be controlled by setting it fixed to the framerate of the headset during testing. This will make sure that any game content behaves as expected even if the system is running in slow motion due to saving every frame as PNG to disk for example. While the system will not drop frames, misses of deadlines set by the framerate can of course still occur. This is an important measure and is recorded herein by querying the VR driver for the number of physical frame presentations every time a frame is completed on the client (see Section 4.3.1 for details).
In summary, we propose that measurements such as image quality estimation will be easier to conduct with the synchronous design, as slow-motion benchmarking is an attribute of the architecture, and the client is guaranteed to receive every rendered frame; an example of this functionality can be observed in [74].

Materials and Methods
Two Windows applications were developed in C++. One of them runs on the client and is connected to Steam VR; this application has no game logic nor geometric rendering functionality. The client polls the HMD pose matrix from the Steam VR driver and sends this matrix to the server, which handles the game logic and renders the scene for two eyes according to the received pose matrix (see Figure 1 for an overview). The server encodes the resulting images of both eyes and sends them back to the client, which in turn decodes the images and finally sends them to the VR driver as OpenGL textures to be displayed in the headset. Note that audio transmission is outside the scope of this work and was not implemented in the prototype.
To ensure that the design is a viable option, we test the prototype system in a range of network environments using various hardware. The system is finally soak-tested in select environments by rendering 100000 frames per session. The soak-tests determine the ratio of stalls, which are compared to those reported in related work. The latter will allow to judge the performance of the synchronous design as compared to state-of-the-art approaches.
3.1. Synchronization. The system contains one main synchronization point between client and display which occurs when polling the HMD pose matrix from the VR driver and decides the framerate of the system. This method is called WaitGetPoses(), is part of the Steam OpenVR API [75], and blocks until a few milliseconds before the start of the next frame, which is referred to as "running start" [76]. Without this sync-point, the system would render without VSync as fast as possible, which would cause tearing.
Synchronization also happens between client and server; the server will block execution until a new input matrix arrives and immediately start rendering upon its arrival. The client will block rendering until two new images, one per eye, have been decoded by the two decoder threads. On completion, the rendering thread will submit the images to the VR driver after resizing (since lower than native resolu-tions are supported). After submitting to the VR driver, the client calls WaitGetPoses() to get a new pose matrix, and the loop is thus complete. If the loop can be completed in less than 11.1 ms, it will operate with zero added latency compared to local VR in the HTC Vive at 90 fps. If the deadline is exceeded, WaitGetPoses() will block for longer and make the system run at 45 fps with a 22.2 ms deadline. In such cases, one might instead run with a delay injection of one frame or lower the resolution to speed up codec processing to try and hit the deadline.

Codec.
The server prototype is designed for use with Nvidia GPUs that have two hardware encoders, e.g., GTX Titan X and GTX 1080 (please refer to [77] for a full list). With two encoder chips, two encoding processes can be utilized fully in parallel, each encoding their corresponding eye simultaneously.
Encoding and decoding are done in C++ with NVENC and NVDEC from the Nvidia Video Codec SDK [71] and CUDA Toolkit. Images are encoded using H.264 with NV12 as video surface format and YUV420 chroma subsampling. An infinite group-of-pictures is used where the frame interval is set to start with one I-frame and thereafter use only P-frames throughout the entire session. This saves bandwidth since the more demanding I-frames can be avoided, but it also makes the solution sensitive to loss, which is why a reliable application layer protocol must be used, for example, reliable UDP or TCP.
The framerate is set to the native rate of the HTC Vive, 90 fps. The VBV buffer size is set to the size of one average frame, as is recommended for low latency operation in the NVENC documentation [71]. Rate control mode is set to NV_ENC_PARAMS_RC_CBR_LOWDELAY_HQ. The size of the encoded image can be changed during execution (see Section 3.4 for details on image sizes). The average bitrate is set to 8 Mbps per encoder for a total of 16 Mbps. This bitrate was selected as it provided sufficient quality at maximum resolution according to SSIM measurements. It should be noted though that between 10 and 16 Mbps per eye should be used depending on expected levels of motion and available resources [74]. Thus, the bitrate used in this work is slightly below recommended levels. This has shown to have a negligible impact on time-consumption though, which is the main focus in this work. For a study relating bitrate requirements to image quality, the reader is referred to [74].
Other than the mentioned modifications, the encoder and decoder have the same configurations as the low latency encoder and decoder samples from the Nvidia Video Codec SDK [71].

Network.
UDP is used to transmit video and input data; two encoder threads transmit video data in parallel from server to client. Input data is transmitted in one packet per frame sent from client to server. In order to guarantee delivery of all UDP packets, we implement our own version of reliable UDP (RUDP) [35]. The RUDP implementation is inspired by Valve's GameNetworkingSockets [78] and the ACK-vector of DCCP [79]. We chose to make our own implementation to make sure we have full control and are 7 International Journal of Computer Games Technology able to optimize it as much as needed. The implementation is designed to quickly respond to loss by being highly sensitive to variations in delay. If a packet is expected and a higher delay than usual is detected, the system will estimate that the packet is lost and triggers a retransmission. In networks with little variation in delay, redundant retransmissions remain rare, and response time on loss remains low. However, redundant retransmissions may occur more often in networks with a large variation in delay.
A detailed presentation of the protocol is outside the scope of this work since the synchronous design does not rely on it per se. TCP with disabled Nagle's algorithm (Nagle's algorithm is a method for TCP to reduce the number of small packets and thus increase bandwidth efficiency. It does so by buffering data that may be intended to be sent immediately in separate packets, this introduces delays in TCP [80]) for example can be used as well or any other RUDP implementation. The effect of such a choice on delay distributions in remotely rendered VR is yet to be studied.

Dynamic Resolution.
The server allocates five frame buffers of different sizes for testing the impact of resolution switches. The resolution levels and sizes are presented in Table 1. The resolutions were arbitrarily determined by subtracting the native resolution by 20% in width and height per level and additionally rounding up to the closest multiple of 16 to avoid cropping in the decoder.

Test Setups.
Experiments were conducted using Windows PC on both server and client. Note that this is naturally not the main target device of future real-world scenarios, and most of the tested client devices could even run desktop VR on their own GPUs. However, they were used in order to gain more control of the testing environment and are sufficient for a proof-of-concept of the proposed method. Future work involves developing a client that can run on, e.g., a phone or stand-alone HMD equipped with hardware decoding capability.
The experiments were conducted in four different environments (see Table 2). The first is referred to as the apartment LAN, where both client and server were on the same LAN/WLAN. The purpose of the apartment experiments was to see how the remote VR solution can operate in a best-case scenario on strong hardware in short-range network conditions, i.e., fog rendering. In this use case, the consumer already has local access to a strong computer for example at home or at an Internet cafe and streams VR to a thin client for example to increase mobility or reduce cost. As previously mentioned, some examples of this from the current market are the low-end remote VR options that stream from PC to phone [2][3][4]. Another similar case is the Oculus Link [10].
The second testing environment was the campus intranet at the Blekinge Institute of Technology (BTH), where client and server were separated by approximately 50 km of optical fiber between two campuses with 1 Gbps bandwidth. These experiments give insight into how the solution may perform in larger networks with longer range but with good routing, i.e., edge rendering. The consumer would in such a scenario not have immediate access to the server, but be closely connected to it through a private intranet for example from home or at an Internet cafe while using a thin client. The intranet would then provide the remote VR service from a remote but optimally routed server with more stability and speed than through the public Internet. In this use-case, for example, a set-top-box could be connected with optimal routing to the remote server, and a VR headset could be plugged into the box or be connected wirelessly. Trials of such a case were conducted by HTC in 2017 [81].
Two experiments were conducted across the public Internet on fiber and 4G. In these tests, the client PC was located in the apartment and the server at the campus approximately 50 km away. These tests were included to reveal to which degree typical contemporary public networks may be able to support this type of remote rendering for VR. A 100/100 Mbps subscription was used for the fiber connection, and an Asus Zenfone 3 Zoom phone was tethered to the client by USB in the 4G testing. In the fiber connection, devices were separated by 18 network hops. This case tests public cloud rendering, which is not only the most flexible option but also most likely to fail due to the high Round Trip Time (RTT) of the public Internet.
Additionally, two experiments using 5G were conducted indoors at the Luleå University of Technology (LTU). The tests show the applicability of this type of remote rendering in an early test bed for the upcoming 5G technology. This use case refers to mobile edge rendering where the rendering server is closely connected to the mobile access point. The 5G experiments were run with an edge-server inside the LTU 5G network [82] connected to a local breakout core (see Figure 2 for details). Four hops were registered between the client and server. An early-release 5G USB modem provided the client laptop with connectivity to the cellular network.
No mobility was tested in any of the wireless networks. The client was only connected to one base station/WiFirouter and did not move to another, in any of the wireless conditions. Also, with the exception of 4G which was outside our control, the client device was also the only device connected to the serving base station/WiFi router during testing.
All experiments were conducted with an HTC Vive VR headset that lied perfectly still on a flat surface while connected to the client computer. To emulate user headset movements in a reproducible way, the HMD pose matrix was rotated in software with an angle that ranged between -180°and +180°at a speed of 90°per second.

Results and Discussion
The results are split up in three test cases. Two relatively short tests were conducted, in which the resolution was altered in run-time in local latency mode and while using International Journal of Computer Games Technology delay injection, respectively. These tests reveal to which degree the codec time consumption affects the rendering loop, and additionally, what the impacts of live resolution switches are on the immediate time-consumption of the following frame. The two tests furthermore provide valuable insight into how the synchronous rendering loop performs in the various networks. This determines whether the networks in question are appropriate for this type of remote rendering. Finally, soak tests were conducted using appropriate settings and environments to reveal the resulting delay distributions and the ratio of stalls over time.

Resolution Tests in Local Latency
Mode. The resolution tests were conducted in all environments and ran for a total of 2500 frames per physical medium. The resolution was reduced one level (20%) after each 500-frame interval. Results show that the decoder time consumption is increased in the moment of a resolution switch, ranging from 1.3 ms to 10.3 ms extra depending on GPU. The encoder suffers no penalty from resolution switches though, but the bitrate is severely increased when such switches take place. Thus, the price to pay for a resolution switch is not only a temporary increase in decoder time consumption but potentially also in video network time consumption, depending on available bandwidth. In our experiments though, we see only negligible increases in video network time consumption at the moment of switches because the available bandwidth can handle the increase. Ordinary video frames generally required around 22 kB in these experiments; frames carrying resolution switches required around 50-60 kB.
Time plots of all resolution experiments are shown in Figure 3. This figure shows the time consumption of each component during execution. The total time consumed from input to display for each frame is shown with the white (Total) line in graphs and takes into account any missing part such as display synchronization and delays. A similar line (blue) shows the time spent between frame presentations on the client (delta time). This time controls the framerate and is the speed at which the game logic is updated. The shown delta time measurement is the average of three connected frames to reduce noise. Ultimately, it is the total time that accurately shows frame stalls, e.g., at spikes. In Figure 3, the total time and delta time are generally the same because no delay injection was used except for in the 5G case, which was included in that figure to save space. The difference between total time and delta time becomes clear in the following Figure 4 where the two are always separate due to delay injection.  Figure 3). The 5 GHz experiment shows a relatively stable run starting at 45 fps at 100% resolution followed by 90 fps at lower resolutions. At 100% resolution though, there is an issue that we refer to as a transition zone, where the framerate should ideally stay at a stable 45 but keeps reaching 90 in recurring bursts. CAT6 provided a stable local latency experience at 90 fps and 100% resolution. The test with CAT6 contained a single frame stall that occurred in the moment of resolution switch from 100% to 80% due to the temporarily increased time consumption of the decoder.

Intranet.
Results show that the wireless media in the intranet supported 45 fps with recurring frame stalls followed by a transition zone at 40% (5 GHz) and 20% resolution (both). The CAT6 connection supported 45 fps without stalls at full resolution (level 0), entered a transition zone at 80%, and ran with recurring frame stalls at the other levels.
The intranet was not able to support a stable local latency remote rendering at native framerate regardless of resolution and physical medium. A stable experience without frame stalls was achieved only at 45 fps with CAT6 and 5 GHz. Note in the graph for CAT6 at 20% resolution that several milliseconds are available before reaching 11.1 ms, but this was  Figure 2: Layout of apartment, intranet, and 5G experiments.  Figure 3. Results show that resolution did not matter in these cases as the majority of time consumption was due to network latency and jitter. The 4G connection supported an unsteady average of around 10 fps. The fiber connection allowed for a stable connection with frame stalls only occurring at resolution switches, but could maintain only 30 fps due to the high latency of the public Internet. This shows the importance of using private infrastructure if one wants to enable synchronous remote rendering. Geographically, there is a few hundred meter difference in client position in the intranet and Internet tests, but the RTT was around 20 ms in the Internet connection and 2-3 ms on the intranet.  In similarity with the Internet tests, the resolution reduction tests over the 5G connection are limited by the RTT. As seen in Figure 3, the majority of the time consumption comes from the network components, i.e., the 5G USB modem and the radio interface itself. Typically, the physical radio layer measures below an average of 14 ms RTT in real-world tests with similar midband Time Division Duplex (TDD) setups using a 3 : 1 downlink/uplink ratio. However, devices such as the USB-modem may add additional delays of around 5-6 ms per direction. This delay is expected to be reduced in upcoming, more optimized user devices. To achieve fiber-like behavior with submillisecond delay on each radio link Ultra-Reliable Low-Latency Communication (URLLC) [83] would have to be used, which is not yet available in this test network.

Resolution
Tests with Delay Injection. The prototype supports injection of one-frame delay. Tests with this functionality were run in the apartment, intranet, and 5G settings with the same parameters as the previously described resolution tests. Except for the test on 5G which is shown in Figure 3 to save space, results from delay tests are shown in Figure 4. Adding a delay of one frame made the system run with little to no frame stalls in all media on LAN. 12 out of 2500 frames were stalled in case of 2.4 GHz but none in case of CAT6 and 5 GHz. Adding a delay in the intranet on CAT6 resulted in zero stalls at a constant 90 fps as well. However, recurring stalls still occurred in both wireless media on the intranet, note the white spikes in total time consumption in Figure 4. These spikes are likely a result of the congested 2.4 and 5 GHz bands in the campus area. Similarly, 5G was not improved significantly by a delay due to the high RTT and spiky network time consumption.

Soak Tests.
Finally, soak tests were conducted in the apartment LAN and intranet environments. In these tests, 100000 frames per medium were recorded at the highest resolution that enabled 90 fps in the resolution tests of the respective medium. On LAN, these were CAT6 (100%), 5 GHz (60%), and 2.4 Ghz (20%). In the intranet, however, only CAT6 was soak-tested since the wireless media failed to maintain a stable framerate both with and without delay in this environment. Two soak tests were conducted with CAT6 on the intranet, one with 20% resolution and one with one frame delay at 100% resolution.   11 International Journal of Computer Games Technology on configuration and acceptable ratio of budget overruns; the data is summarized in Table 3. The table provides a detailed overview by showing the budget requirement of both network components at each labeled percentage. For example on LAN with CAT6 (test A), a budget of 0.9 ms covers the requirement of the video component in all but 0.01% of frames. To maintain the same level of overruns in 5 GHz at 60% resolution (test B), a budget of 7.3 ms would be required. In addition to budgets, the table shows how many frame stalls occurred during the test, e.g., 0.009% of frames in CAT6 on LAN. To provide maximum accuracy, we used Steam VR to measure the number of stalls. They were determined by querying the VR compositor through the OpenVR API for the variable "Compositor_FrameTiming::m_nNumFramePresents" at each frame and adding its value to the total number of stalls. A number larger than one is regarded as one or more frame stalls, because the same frame was then presented multiple times.
The table further shows the average framerate, bitrate, and total time consumption per frame. Note that the true fra-merate of the HTC Vive is not exactly 90 fps but 89.53 fps [84]. Thus, the framerate of test A, 89.52 fps, is close to optimal but suffered nine frame stalls which resulted in a lower average framerate. Test E shows an optimal framerate of 89.53 fps though when rounded to two decimals.
The bitrate is also affected by the number of stalls, because when framerate is lowered by half, so is the effective bitrate. This can for example be seen in test C (2.4 GHz) where the average bitrate is 15.0 Mbps due to a relatively high number of frame stalls of 3.220%. The effective bitrate is also affected by the number of redundant UDP retransmissions, which is why it can reach above the set 16.0 Mbps. The average total time consumption per frame is also shown, which should optimally be 11.169 ms due to the true framerate of 89.53 fps.   International Journal of Computer Games Technology of one frame was able to provide a stream with 0.002% stalls. These are improvements over previous work [22] which reported a frame missing rate of 0.1-0.2% as well as the industry example that showed 0.3% frame drops [72].

Conclusions and Outlook
We have shown one way to design a synchronous remote rendering VR system that solves the synchronization problem between client and server and thus eliminates a source of frame stalls. By testing an implementation of this design, we have quantified the ratio of stalls, identified, and shown some conditions under which it may be operated and what requirements it poses on supporting hardware. We conclude that the architecture can run well with a latency equal to local VR, i.e., in local latency mode. However, a stable network with low latency must be used in order to stream in that mode reliably. The campus intranet we used did not suffice, and neither did the public Internet nor the early 5G test network. Only on LAN could a stable local latency operation be achieved at the native resolution and framerate of the HTC Vive. On LAN/WLAN, the network was not the major issue, but the encoder and decoder time consumption. Indeed, apart from network delay spikes, the encoder time is generally the bottleneck of the system, especially at high resolutions. Decoding in our experiments generally took less than 2 ms while encoding could take up to 6 ms. Reducing the resolution to 20% of native size would in general reduce encoding to around 1.5 ms and decoding to around 1 ms, which was shown to be useful to meet the deadline in some scenarios, but will of course have a negative impact on video quality. In case the local latency deadline cannot be kept, the architecture supports injection of full frames of latency, i.e., an added latency of 11.1 ms per frame at 90 fps. Delay injection proved to make streaming more reliable in environments where this was sufficient to compensate for the jitter of the network. We expect that the precise addition of latency may help when adding future motion prediction.

Limitations.
We have not taken into account two parts that are outside our scope, but are otherwise important parts to consider in remote rendering for VR. They are the following: Simple Game: The game used in our experiments is a simple 3D scene in which boxes surround the player in a small room. This scene and game logic are not complex and often required less than 1 ms to compute and render. In a realworld scenario, the game would likely require at least a few milliseconds on average, which would have to be taken into account when calculating budgets.
No Audio: We have ignored audio in the implementation of this system. In a real scenario, more data containing the audio would have to be sent from the server to client each frame.
Furthermore, to account for lens distortion in the HTC Vive, it is advisable to render at 1.4x the native resolution (1512 × 1680 instead of 1080 × 1200). However, to avoid transmitting such large images, at 100% resolution in tests.
Rendering was conducted at 1.4x the size on the server but lens distortion was applied before encoding, thus reducing the size of the images and the amount of data processed by the codec and network. To do this though, one must also disable the lens distortion that is normally applied in the VR driver on the client. This will also disable any built-in image warping functionality, which exists to reduce the perceived rotation and/or translation latency. Thus, it would be better to just transmit non lens-distorted images at the native size and accept a loss in pixel density instead of disabling warping. Whether lens distortion is applied on server or client does not visibly affect the results presented in this work though. But future work may address this issue for example by using foveated video processing [85,86] which is how it is addressed in the Oculus Link [10].

Future
Work. Local latency mode, while difficult to support with a codec, may be perfectly viable if the time for encoding and decoding can be neglected, which may be the case if for example a very high bandwidth is available, requiring little to no compression. This is the case with the wireless VR adapters that are available on the market today, which typically utilize the 60 GHz band with for example 802.11ad [87].
Although 802.11ad in theory supports up to 8 Gbps [88], it does not support compression-less remote rendering for the resolutions and framerates of current generation HMDs, e.g., the Valve Index. To solve this issue, one may look forward to the next generation of 60 GHz WiFi known as 802.11ay [88]. 802.11ay is at the time of writing in development [89] and aims to support up to 100 Gbps [88]. The article that announces 802.11ay puts the VR use-case in focus, part of its abstract reads: "While enabling multi-Gb/s wireless local communications was a significant achievement, throughput and reliability requirements of new applications, such as augmented reality (AR)/virtual reality (VR) and wireless backhauling, exceed what 802.11ad can offer." [88].
The prototype was so far tested with 802.11 ac (denoted as 5 GHz for short) and 802.11n (2.4 GHz). How will the architecture perform in more sophisticated wireless networks? Similar measurements could be conducted using for example 802.11ad, 802.11ay, 802.11ax, or 5G with URLLC enabled [90].
Applying lens distortion on the server is not optimal due to the interference with image warping techniques. Encoding and transmitting supersampled images is on the other hand time-consuming for the codec due to the data size. Smaller images may therefore be used in conjunction with superresolution [91] or foveated encoding [36], the latter of which is already applied in the Oculus Link [55]. How much speedup can we get from these technologies and to what level of detriment to the image quality?
The presented work determined that the ratio of frame stalls could be reduced with a synchronous design. What ratio of frame stalls are noticeable to users though? Subjective QoE-studies may be conducted to answer this question. 13 International Journal of Computer Games Technology

Data Availability
Data and code are available at https://github.com/kelkka/ RemoteRenderedVR. If the linked page should be unavailable, data and code will be made available on request through the email listed on the title page (viktor.kelkkanen@bth.se).

Conflicts of Interest
In the tests with a 5G connection, we have used a 5G test-site using equipment developed by Ericsson. This may be perceived as a conflict of interest since one of the authors is employed at this company.


extfieldsofstudy:
Computer Science
Medicine

text:
An Entropy Metric for Regular Grammar Classification and Learning with Recurrent Neural Networks

Recently, there has been a resurgence of formal language theory in deep learning research. However, most research focused on the more practical problems of attempting to represent symbolic knowledge by machine learning. In contrast, there has been limited research on exploring the fundamental connection between them. To obtain a better understanding of the internal structures of regular grammars and their corresponding complexity, we focus on categorizing regular grammars by using both theoretical analysis and empirical evidence. Specifically, motivated by the concentric ring representation, we relaxed the original order information and introduced an entropy metric for describing the complexity of different regular grammars. Based on the entropy metric, we categorized regular grammars into three disjoint subclasses: the polynomial, exponential and proportional classes. In addition, several classification theorems are provided for different representations of regular grammars. Our analysis was validated by examining the process of learning grammars with multiple recurrent neural networks. Our results show that as expected more complex grammars are generally more difficult to learn.

Introduction
Regular grammars (RGs) have been widely studied in the theory of computation and intensively applied in natural language processing, compiler construction, software design, parsing and formal verification [1][2][3][4]. Despite their importance and pervasiveness, there is limited research [5][6][7] investigating the internal structure of regular grammars. As such, our understanding of regular grammars is relatively coarse-grained.
One approach to understand a more fine-grained understanding of regular grammars is to investigate them through machine learning. Recent research has demonstrated that recurrent neural networks (RNNs) can achieve superior performance in a wide array of areas that involve sequential data [8], e.g., financial forecasting, language processing, program analysis and particularly grammatical inference. Specially, recent work has shown that certain types of regular grammars can be more easily learned by recurrent networks [9,10]. This is important in that it provides crucial insights in understanding regular grammar complexity. Furthermore, understanding the learning process of regular grammar also help differentiating different recurrent models [11][12][13].
Our intent is to establish a closer connection between the complexity of regular grammars and machine learning tasks from both theoretical and empirical perspectives. From a theoretical perspective, we regard classification and representation as two fundamental problems (Izrail Gelfand once remarked, "all of mathematics is some kind of representation theory" [14]). We follow previous work [15] by studying a grammar from its concentric ring graph representation, which contains sets of strings (with a certain length) accepted and rejected by this grammar. Note that this representation can be used for any grammar.
An entropy value is then introduced based on the properties of the concentric ring graph that categorizes all regular grammars into three classes with different levels of complexity, and further establishes several classification theorems based on different representations of regular grammars. In addition, through an empirical study, different regular grammars are categorized by applying them to a set of learning tasks. That is, given enough positive (accepted) and negative (rejected) string samples of a specific regular grammar, it is expected that machine learning models will gradually identify a latent pattern of a grammar through the training process. This shows that this indeed reflects the difficulty of learning regular grammars and highly depends on the complexity of a grammar. All RNNs were evaluated and compared on string sets generated by different RGs with different levels of complexity so as to explore the characteristics of each regular grammar. As such, the empirical results become well aligned with the theoretical analysis. It is hoped that these results can provide a deeper understanding of a regular grammar under a learning scenario as well as practical insights into its complexity.
In summary, the contributions of this paper are as follows: • We propose a new entropy metric for measuring the complexity of regular grammar in terms of machine learning which reflects the internal structure and hence provides a fine-grained understanding of a regular grammar. • We categorize regular grammars into three disjoint subclasses based on the entropy value with several classification theorems for different representations proved. • We empirically demonstrate the validity of the proposed metric and corresponding classification by a series of experiments on the Tomita grammars.
The rest of the paper is organized as follows. Section 2 provides preliminary and background material on recurrent neural networks and regular grammars. Section 3 surveys relevant work on complexity and classification of regular grammars. Section 4 presents our complexity metric and categorization results with several theorems based on different representations proved. Case study and experimental results are shown in Sections 5 and 6, respectively. Section 7 is the conclusion and future work.

Preliminaries
First, there is a brief review of fundamental recurrent neural machine learning models. The definition of regular grammars is then introduced, followed by the set of Tomita grammars that are used in this study.

Recurrent Neural Networks
A unified view of the update activity of recurrent neurons for different RNNs investigated is shown in Table 1. Typically, a RNN consists of a hidden layer h containing N h recurrent neurons (each designated as h i ) and an input layer x containing N x input neurons (each designated as x k ). The values of h at tth and t−1th discrete times are denoted as h t and h t−1 . Then, the hidden layer is updated by: where φ is the activation function (e.g., Tanh and Relu) and W denotes the weights which modify the strength of interaction among input neurons, hidden neurons, output neurons and any other auxiliary units. The hidden layer update for each RNN is presented in Table 1. Next, we describe fundamental RNN models used in our analysis.

Elman Network (SRN)
SRN [16] integrates the input layer and the previous hidden layer in a manner that is regarded as a "first-order" connection [17]. This first-order connection has been widely adopted for building different recurrent layers, for example the gate units in LSTM [18] and GRU [19]. Table 1. Hidden update of RNNs selected; building blocks for developing many complicated models. Let W * , U * and V * denote weights designed for connecting different neurons and b denote the bias.
is the Hadamard product. [20] have second-order connections in their recurrent layers and are designed to capture more complex interactions between neurons. The 2-RNN has a recurrent layer updated by a weighed product of input and hidden neurons. This type of connection enables a direct mapping between 2-RNN and a DFA [21]. Recent work [22] also shows the equivalence between a 2-RNN with linear hidden activation and weighted automata. Related work [23,24] used weighted automata to explore the relationships between deep learning and grammatical inference. Since a 2-RNN has a 3D tensor weight, computation is more intensive. As such, various approximations (M-RNN with a tensor decomposition [25] and MI-RNN with a rank-1 approximation [26]) have been proposed to alleviate the computational cost while preserving the benefits of high order connections for better modeling the complicated recurrent interaction.

RNNs with Gated Units
LSTM [18] and GRU [19] were proposed to deal with the vanishing and exploding gradient problems of SRNs. While these RNNs are effective for capturing the long-term dependence between sequential inputs, their gate units induce highly nonlinear behavior to the update of the hidden layer which creates difficulty in analysis.

Regular Grammar
A regular grammar (RG) recognizes and generates a regular language-a set of strings of symbols from an alphabet-and is uniquely associated with a deterministic finite automata (DFA) with a minimal number of states [27]. For a more thorough and detailed description of regular language and finite state machines, please refer to the work of Hopcroft et al. [27]. The Tomita grammars [28] denote a set of seven regular grammars that have been widely adopted in the study of grammatical inference [29]. Even though the Tomita grammars are relatively simple, they cover regular languages that have a wide range of complexities. and have been widely used as benchmarks [30][31][32] for grammar learning. These grammars all have alphabet Σ = {0, 1} and generate infinite languages over {0, 1} * . For each Tomita grammar, the binary strings generated by this grammar are its associated positive samples and the rest of the binary strings as negative samples. A description of the positive samples accepted by all Tomita grammars is shown in Table 2. It is important to realize that DFAs cover a wide range of languages, which means that all languages whose string length and alphabet size are bounded can be recognized and generated by a DFA [20]. It is worth noting that regular grammars and finite state machines have many practical uses in mechanical and electrical engineering and software. (10)* 3 an odd number of consecutive 1 s are always followed by an even number of consecutive 0 s 4 any string not containing "000" as a substring 5 even number of 0 s and even number of 1 s 6 the difference between the number of 0 s and the number of 1 s is a multiple of 3 7 0 * 1 * 0 * 1 *

Related Work
Here, we briefly discuss RNNs and regular grammars. We also revisit several complexity measure and some traditional representations of the regular grammar in automata theory.

RNNs and Regular Grammars
Grammars and automata and neural networks have been intertwined since McCulloch and Pitts' early 1943 paper [33], which led to Kleene's work [34] on regular grammars. Minsky's dissertation [35] extended this to models of neural networks and automata. With the rebirth of neural networks, much work on recurrent networks and finite state automata [16,20,36,37] was restarted. Since then, there has been theoretical work on Turing equivalence [38] and finite state machine encoding and representation [39]. The computational hardness of some of the representation results have recently been discussed [12]. Recently, there has been a renewed interest in extracting learned DFA from recurrent neural networks [31,40,41]. Such methods can be important for verification for neural networks and explainable AI [4,42] There has been an increase in the natural language processing community on revisiting formal language models [43]. Because of their wide use and applications, we only focus on regular grammars.

Complexity of Shift Space
In symbolic dynamics [44], a particular form of entropy is defined to measure the "information capacity" of the shift space, which is a set of bi-infinite symbolic sequences that represent the evolution of a discrete system. When applied to measure the complexity of a RG, this entropy describes the cardinality of the strings defined by its language.

Logical Complexity
RG can also be categorized according to logical complexity [45]: strictly local (SL), strictly piecewise (SP), locally testable (LT), etc. These classes have multiple characterizations in terms of logic, automata, regular expressions and abstract algebra [6]. SL and SP languages are the simplest and most commonly used languages that define a finite set of factors and subsequences, respectively, and are selected to evaluate different RNNs on their performance in capturing the long-term dependency [6]. Unlike logical categorizations of regular grammars, we evaluate the complexity in terms of machine learning tasks.

Representations of Regular Grammars
Automata theory has a close connection to many different mathematical subjects such as symbolic dynamics, group theory, algebraic geometry, topology and mathematical logic [46]. Hence, a regular grammar has different representations based on these perspectives. A description of several commonly used representations is shown in Figure 1. We introduce the necessary concepts when they are used in the paper.

Entropy and Regular Grammars
It is important to note that the concept of entropy was introduced in the field of grammatical inference to solve different tasks [47,48] and more recently for distilling weighted automata [49]. Unlike those definitions, our definition originates in the graphical representation of regular grammar and gives insight into a metric for evaluating RNN learning and DFA extraction.

Categorization of Regular Grammars
This section reviews the concentric ring representation of regular grammar, and, using this representation, we introduce an entropy metric to evaluate their complexity. All RGs are then categorized into three classes according to their entropy values. Last, we provide several classification theorems of RGs in terms of their different representations. A flowchart of our analysis is shown Figure 2.

RG Categorization
Set DFA Generating Function

Order relaxation
Entropy value Representation Application Evaluation Figure 2. Flowchart of analysis.

Entropy of a Regular Language from an Concentric Ring Representation
The concentric ring representation [15] of a regular grammar reflects the distribution of its associated positive and negative strings within a certain length. Specifically, in each concentric ring, all strings with the same length are arranged in lexicographic order where white and black areas represent accepted and rejected strings respectively. Three ring graphs for Tomita Grammars 1, 3 and 6 are shown in Figure 3 to illustrate their differences. In each graph, every concentric ring contains the sets of strings and its following strings at a specific length that are accepted and rejected by its RG. Note that the percentages of accepted (or rejected) strings for different grammars are very different. For example, Grammars 3 and 6 have the numbers of accepted strings much larger than that of Grammar 1. This difference in prior empirical work [31,41] showed that Grammar 6 is much harder to learn than Grammars 1 and 3. An intuitive explanation is that, for Grammar 6, flipping any 0 to 1 or vice versa means any accepted or rejected string can be converted into a string with the opposite label. A RNN needs to learn such subtle changes in order to correctly recognize all strings accepted by Grammar 6. Since this change can happen to any digit, a RNN must account for all digits without neglecting any.

Grammar 1
Grammar 3 Grammar 6 We now formally show that a RG that generates a more balanced set of accepted and rejected strings has a higher level of complexity and appears more difficult to learn. Given an alphabet Σ = {0, 1}, the collection of all 2 N strings of symbols from Σ with length N is denoted as X N . For a grammar G, let m N p (r N p ) and m N n (r N n ) be the numbers (ratios) of positive and negative strings, respectively. The constraint that all strings are arranged in a lexicographic order is relaxed, which indicates that all strings in X N are randomly distributed. We then denote the expected times of occurrence for an event F N -two consecutive strings having different labels-by E[F N ]. This gives the following definition of entropy for RGs with a binary alphabet.

Definition 1 (Entropy).
Given a grammar G with alphabet Σ = {0, 1}, its entropy is: where H N (G) is the entropy calculated for strings with the length of N. (Here, we use lim sup for certain particular cases, i.e., when N is set to an odd value for Grammar 5.) .
Furthermore, the following proposition to efficiently calculate the entropy by expressing E[F N ] explicitly becomes: Proof of Proposition 1. Given any concentric ring (corresponding to the set of strings with a length of N) shown in Figure 3, let R denote the number of consecutive runs of strings and R p and R n denote the number of consecutive runs of positive strings and negative strings in this concentric ring respectively. Then, we have E Without loss of generality, we can choose the first position as θ = 0 in the concentric ring. Then, we introduce an indicator function I by I i = 1 representing that a run of positive strings starts at the ith position and As such, we have By substituting E[F] into the entropy definition, we have Thus, the metric entropy is well-defined and lies between 0 and 1. Proposition 1 implies that the entropy of an RG is equal to the entropy of its complement, which confirms our intuition in terms of learning task. Without loss of generality, we assume from now on that for all RGs the set of accepted strings has a smaller cardinality. In addition, we conclude that an RG generating more a balanced string sets has a higher entropy value. As such, we can categorize all RGs with a binary alphabet based on their entropy values.  When compared to the entropy in shift space, which only considers accepted strings, our Definition 1 considers both the accepted and rejected strings. This is more informative and has other benefits. For example, given a dataset with samples uniformly sampled from an unknown dataset, we can then estimate the complexity of this unknown dataset by calculating the entropy of the available dataset. For a k-class classification task with strings of length N, let m i denote the number of strings in the ith class. Then, we have We can then generalize Definition 1 to a k-class classification case by substituting this into Definition 1. However, this can be challenging for the entropy defined for shift space since it can only be constructed in a one-versus-all manner. In addition, the shift space cannot express all RGs, especially for grammars that lack shift-invariant and closure properties [44].

Set Representation
Here, we conduct a combinatorial analysis. Given a regular grammar G, we consider it as a set and explore the property of its cardinality. Namely, we have the following theorem: Theorem 1. Given any regular grammar G with Σ = {0, 1}, we have: (a) G belongs to [Po] if and only if m N p ∼ P(N), where P(N) denotes the polynomial function of N; Here, ∼ indicates that some negligible terms are omitted when N approaches infinity.
Proof of Theorem 1. In both Definition 2 and Proposition 1, lim sup is used to cover certain particular cases, for instance when N is set to odd value for Grammar 5. In the following proof, without loss of generality, lim is used instead of lim sup for simplicity. According to Proposition 1, for any regular grammar G, its entropy H(G) ∈ [0, 1]. It can be checked that the maximum value of H(G) is 1 when r N p = 0.5. In addition, the minimum value of H(G) is 0 and can be reached when r N p = 0 or 1. However, r N p = 0 or 1 are only allowed for grammars that either accept or reject any string, hence are not considered in this theorem. As such, in this case, the value of entropy is taken as the minimum when In the following, we only discuss the former case and the latter can be similarly derived.
For each class of grammars, given that their m p takes the corresponding form shown in Theorem 1, the proof for the sufficient condition is trivial and can be checked by applying L'Hospital's Rule. As such, in the following, we only provide a proof for the necessary condition.
From (4), we have: where m p denotes the derivative of m p with respect to N. It is easy to check that lim N→∞ m p m p exists for regular grammars. Then, we separate the above equation as follows: It should be noted that the second term in the above equation equals 0. Specifically, assuming that m p has the form of α · b N where b < 2 (b cannot be larger than 2 for binary alphabet), then the denominator of the second term is infinity. If m p has the form of α · 2 N , then the numerator tends to zero while the denominator is finite. As such, we have If H(G) = t = 0, then we have lim N→∞ ln(m p ) Theorem 1 shows the reason for naming these subclasses. In addition, when a specific order is posed on the set of given RG, we have a similar result from number theory. Specifically, given a string s = x 1 x 2 x 3 · · · x N with length N, we associate the string with a decimal number, i.e., D s = ∑ N i=1 x i · 2 i−1 + 2 N − 1. Note that this formula is different from the traditional approach to transforming a binary number to a decimal number, since 0 has physical meaning in regular grammar. For example, 000 is different from 00 in regular grammar. That is the reason that we need an additional term term 2 N − 1 to differentiate these situations. In this way, D s has induced an order on the regular grammar. Let D n s denote the nth smallest number in this set; then, we have the following result: Here, B n = log 2 n/ log 2 D n s .
Here, we provide a brief explanation of Corollary 1. The denominator approximates the length of the string and the numerator represents the cardinality of the set. Hence, comparing with the original Definition 2, this corollary provide an alternative perceptive of entropy. Take Tomita Grammar 1 for example. The set is G = { , 1, 11, 111, · · · } with the number D s = {0, 2, 6, 14, · · · }, and the formula for D n s is given by D n s = 2 n − 2; hence, by simple calculation, we find that the limit of the ratio is 0 when n approaches to infinity, which implies that Grammar 1 belongs to the polynomial class. Note that in general it is difficult to calculate the explicit formula for D n s and therefore Corollary 1 has certain limitation in practical applications.

DFA Representation
Here, we provide an alternative way to obtain the classifications for RGs using the transition matrices of its associated minimal DFA [27] in terms of states. This approach provides immediate results if the minimal DFA is available. As such, this reduces the computation cost of a data-driven approach. Here, we again use the case when the alphabet size is two. However, it is easy to extend this for grammars with larger alphabets. Given a regular grammar G with the alphabet Σ = {0, 1} and its associated minimal complete DFA M with n states, let T 0 , T 1 ∈ Z n×n denote the transition matrices of M associated with input 0 and 1, and the transition matrix of the DFA is defined as T = T 0 + T 1 . Alternatively, the transition matrix of a given DFA can be considered as the transition matrix of underlying directed graph by neglecting the labels associated with the edges. With the above settings, we have the following theorem: Proof of Theorem 2. We first introduce a lemma which is used in the proof.

Lemma 1.
Let v 1 and v 2 denote two one-hot encoded column vectors corresponding to a starting state and an ending state of a DFA respectively. One can construct an adjacent matrix P for this DFA by regarding it as an undirected graph with each node represents a state and every edge represents the existence of a transition between a pair of states. Then, the number of L-length strings that reach the ending state v 2 from v 1 is v T 1 P N v 2 .
Based on the lemma above, it is easy to see that the number of positive strings is m p = v T 1 P N q where q is a one-hot encoded column vector representing an accepting state. By applying Jordan decomposition to P, i.e., P = SJS −1 , we can see that m p = v T 1 SJ N S −1 q and J N is the only term depending on N. Specifically, take one Jordan block J i ∈ R m×m with the eigenvalue of λ and let K i denote the nilpotent matrix associated with J i , that is, the superdiagonal of K i contains ones and all other entries are zero. Then, we have: It is easy to see that when the absolute of the eigenvalue, i.e., |λ| = 1, J i (λ) N has a polynomial form of N. This result can be generalized to all Jordan blocks of J. As shown in the proof of Theorem 1, this corresponds to the case when G belongs to the polynomial class (we omit the proof since the number of diagonal elements of T equal to 2 is 1, as discussed in the paper). Denote the second largest eigenvalue of T as b, then β · b N dominates m p , where β is some constant. As such, one can easily derive the proof by following the proof for the exponential class in Theorem 1.
Theorem 2 indicates that the entropy of a RG lies in the spectrum of its associated DFA. Specifically, in the polynomial and exponential classes, a DFA with its summed transition matrix T having only one diagonal element that is equal to 2 indicates that this DFA has only one "absorbing" state (either the accepting state or the rejecting state). Assume that a DFA has one absorbing state and is running over a string. Once reaching the absorbing state, this DFA makes a permanent decision-either acceptance or rejection-on this string, regardless of the ending symbol has been read or not. In comparison, in the proportional class, a DFA can have either zero or two absorbing states (one accepting state and one rejecting state). In the case of Tomita grammars, every grammar has exactly one absorbing state except for Grammars 5 and 6, which have no absorbing states. The DFAs for Grammars 5 and 6 can only determine the label of a string after processing the entire string.
Recall that we require that for all RGs the set of accepted strings has a smaller cardinality. As such, the incomplete DFA for a given RG can be obtained by deleting the rejecting absorbing state and all the edges associated with the state from a minimal complete DFA. (This is important since for a proportional class there might exist two absorbing states and the accepting absorbing state in that case cannot be deleted. A more significant result is that, in the monoid representation of regular grammar, only the monoid associated with polynomial and exponential grammar is a nulloid. The discussion of monoid representation is out scope here.) Similarly, the transition matrixT of the incomplete DFA becomes: Here, L(T) denotes the largest eigenvalue ofT.
Corollary 2 together with Theorem 2 provides a complete analysis of classification results for a DFA representation. It is easy to see that neither strictly local or strictly piecewise belongs to the proportional class since they all have one absorbing-rejecting state. They can be categorized into either the polynomial or exponential class according to their specific forbidden factors or subsequences. Please refer to classification theorems of regular grammars with arbitrary alphabet size in Appendix B.

Generating Function Representation
Now, we derive the classification results based on the generating function representation of a regular grammar. A generating function encodes an infinite sequence of numbers by treating them as the coefficients of a power series, which is widely applied in combinatorial enumeration. Specifically, the generating function of regular grammar is defined as follows: An important result is that generating function of regular grammar is a rational function. We have the following theorem for classification: The theorem can be understood from two perspectives. First, from Theorem 1, we can readily derive the radius of convergence by a ratio test. Another is related to calculating the generating function from a DFA. Specially, we have the following lemma [50]: The generating function f ij (x) from state i to state j is given by where (B : j, i) denotes the matrix obtained by removing the jth row and ith column of B.
Note that the radius of convergence r only depends on the denominator of the function f (x), and r is the smallest pole of the function. By Lemma 2, the denominator has the form det(I − xT). As such, the radius is the inverse of the largest eigenvalue of the transition matrix. The classification theorem is a generating function of a regular grammar and can be easily generalized to a regular grammar with multiple alphabets.

Regular Expression Representation
Here, we provide an analysis from a regular expression perspective. First, we consider the following interesting question: Given a regular grammar, how many parameters does one need to uniquely determine a positive string? The question is closely related to automatically generate positive samples by computer. We start with a simple example. For Tomita Grammar 7, we have G = 0 * 1 * 0 * 1 * , and we only need four numbers a, b, c, d to generate a string 0 a 1 b 0 c 1 d . However, for a more complicated example Tomita Grammar 4, we have G = ( + 0 + 00)(1 + 10 + 100) * , and, in this case, we have to record both the number and location of the suffix string 1, 10, 100 separately. Hence, we need Z 3 numbers to generate a sample. Moreover, we have the following fact: Here, k is a constant and N(G) denotes the required number of parameters.
Another perspective to explore this problem is to apply group theory. Specifically, given a regular grammar, we can consider it as a topological space. Furthermore, it can be decomposed into several disjoint orbits of different base points, and the whole topological space is generated by the actions on these base points. In this way, these actions form a monoid and the cardinality of the monoid reflects the complexity of the grammar. Again, we use Tomita Grammars 4 and 7 as an example to illustrate this idea. For G = 0 * 1 * 0 * 1 * , the base point of the topological space is and we define the following different actions: h 1 , adding 0 in the first slot; h 2 , adding 1 in the second slot; h 3 , adding 0 in the third slot; and h 4 , adding 1 in the fourth slot. Note that first adding 1 in the second slot and then adding 0 in the first slot is exactly the same as first adding 0 in the first slot and then adding 1 in the second slot, which means that these actions commute to each other. Hence, this monoid is an abelian monoid (more formally, this monoid can be considered as the quotient of a free monoid by a normal submonoid, i.e., and the cardinality of the monoid is Z 4 . For G = ( + 0 + 00)(1 + 10 + 100) * , the base points are , 0 and 00, and we define the following actions: h 1 , attaching 1 in the back; h 2 , attaching 10 in the back; and h 1 , attaching 100 in the back. Note that this monoid H is no longer commutative, since h 1 h 2 acting on base point 0 gives the string 0101 while h 2 h 1 acting on base point 0 gives the string 0011. Hence, in this case, the monoid is a free monoid generated by h 1 , h 2 , h 3 and the cardinality of this monoid is 3 Z . More generally, we have the following fact:

Case Study for Tomita Grammars
As our goal is to study the characteristics of subclasses of regular grammar in terms of machine learning, we use the often cited Tomita grammars [51] as examples for our analysis, which is consistent with the evaluation. For each classification result in Section 4, we choose an example to illustrate its application. The full results for the Tomita grammars are listed in Table 3.

Set Representation
Here, we use Tomita Grammar 3 to illustrate the application of Theorem 1. Note that, in Table 3, we can see that it is difficult to derive an explicit formula for m N p from a pure combinatorial approach. Instead, we provide a brief proof that Grammar 3 belongs to exponential class. Let G N denote the set of positive samples with length N, and it is easy to notice that it can be decomposed into the following four disjoint sets: samples ending with consecutive even numbers of 1 s, samples ending with consecutive odd numbers of 1 s, samples ending with 0 s and the number of 0 s at the end limited by the constraint, and samples ending with 0 s and the number of 0 s at the end not limited by the constraint. We use A N 1 , A N 2 , A N 3 ,and A N 4 to denote these sets, respectively. Hence, we have that Furthermore, we have the following recursion formulas: where [·] denotes the floor function and the initial condition is A 0 1 = 0, A 0 2 = 1, A 0 3 = 0, and A 0 4 = 1. By adding these formulas, we have m N p = m N−1 , which implies that this sequence increases faster than Fibonacci sequence. Hence, it cannot belong to the polynomial class.
In contrast, let Z 1 denote the event that an even number of 0 s followed by odd number of 1 s and Z 2 denotes the event that even number of 0 s always followed by odd number of 1 s in the whole string. Hence, when the length of the string N approaches infinity, the expectation of the probability of Z 2 is an infinite product of probability of Z 1 , which approaches zero. The indicates that the ratio of positive samples approaches zero when N approaches infinity. Thus, m N p does not contain the term α · 2 N . Finally, we conclude that this grammar belongs to exponential class.

DFA Representation
Here, we use Tomita Grammar 2 to illustrate the application of Theorem 2. The transition matrix of the complete DFA is T =

Generating Function Representation
Here, we use Tomita Grammar 4 to illustrate the application of Theorem 3. The generating function is f (x) = 1+x+x 2 1−x−x 2 −x 3 , and the radius of convergence is the smallest positive pole of the function. Namely, we need to solve the equation x 3 + x 2 + x − 1 = 0 and we have r = 0.544, which lies between the values of 0 and 1. Hence, it belongs to the exponential class.

Evaluation
Here, our empirical results show that the categorization of RGs is related to the difficulty of RNNs to learn these grammars, and the implementation is publicly available (https://github.com/lazywatch/rnn_theano_tomita.git). We evaluated the three Tomita Grammars 1, 3 and 5. For each grammar, its subclass is shown in Table 3. Following prior work [31], we generated three training sets of binary strings with their lengths ranging from 1 to 14 for these grammars. We also collected three validation sets of strings with different lengths of [1, 4, 7, . . . , 25], to make sure that the models can be trained to generalize to longer strings. The training process was terminated either when the model achieved a F 1 -score that is equal or higher than 0.95 or when a maximum of 5000 epochs were reached. We selected several different recurrent networks to demonstrate how the difficulty of learning generalizes to different models. Specifically, we trained SRN, 2-RNN, GRU and LSTM with data generated on each grammar to a perform a binary classification task. We configured all RNNs to have the same size of hidden layer across all grammars and trained them on each grammar for 10 random trials using a mean squared error loss. In each trial, we randomly initialized the hidden layer of the model.
We followed previous research [20] and used either activation functions-sigmoid and tanh-to build these RNNs. In addition, for each RNN, we used one-hot encoding to process the input alphabets of 0 s and 1 s. With this configuration, the input layer is designed to contain a single input neuron for each symbol in the alphabet of the target language. Thus, only one input neuron is activated at each time step. Moreover, we followed the approach introduced in previous research and applied the following loss function to all RNNs: This loss function can be viewed as selecting a special "response" neuron h 0 and comparing it to the label y, i.e., 1 for acceptance and 0 for rejection. Thus, h T 0 indicates the value of the neuron h 0 at time T after a RNN receives the final input symbol. By using this simple loss function, we attempt to eliminate the potential effect of adding an extra output layer and introducing more weight and bias parameters. In addition, by this design, we ensure that the knowledge learned by a RNN resides in the hidden layer and its transitions. When applying different activation functions, we make sure that h 0 is always normalized between the range of 0 and 1, while other neurons have their values between 0 and 1 for sigmoid activation and −1 to 1 for tanh activation. During training, we optimized parameters through stochastic gradient descent and employed RMSprop optimization [52].
The results are shown in Figure 5, where the results from all trials fit the shaded area associated with each plot. The x-axis represents the number of epochs during training and the y-axis represents the loss. In Figure 5a-d, we see that Grammars 1 and 3, which have lower entropy values, have learning that converges much more quickly and consistently than that of Grammar 5, which has the highest entropy value. This effect holds for all RNNs evaluated. Note that Grammar 5 defines two sets of strings with equal cardinality when the string length is even. In this case, by flipping any binary digit of a string to its opposite (e.g., flipping a 0 to 1 or vice versa), a valid or invalid string can be converted into a string with the opposite label. This implies that a model must pay equal attention to any string in order to learn the underlying grammar, which makes the learning process more challenging. To better illustrate the difference of the difficulty of learning Grammars 1 and 3, a zoomed view is provided in Figure 5e-h, for each plot at the top row of Figure 5. While the learning process of all models converges within 100 epochs for both grammars, it is clear that the learning process is slower for Grammar 3. These results agree with both our analysis of the entropy of these grammars and our intuition.
It would be interesting to further investigate the relationship between recurrent models and grammar learning, which is out of the scope for this paper. A promising approach would be to investigate their connection is to more closely represent DFA representations, since both are stateful models. In general, while it is possible to validate the connection between nonlinear RNNs and DFAs empirically, it has been challenging to establish a theoretical connection between nonlinear RNNs and finite state machines. Specifically, second-order RNNs naturally fit into the task of learning any DFA, while some first-order RNNs only represent a portion of DFAs, indicating that the gap (not computationally) between first-/second-order RNNs is not as significant as expected. However, for these gated models (LSTM/GRU), we only observe the differences by experiments.
From the evaluation results, a more general question is to establish an analysis between different types of RNNs and DFAs. To better study this, we discuss the following two questions: Given a RG, does there exist some common substrings misclassified by different RNNs? Given a RNN, are there consistent persistent flaws when learning different RGs? Our results observed on the Tomita grammars can be considered as an initial attempt to answer the above questions. We first find that all RNNs perform perfectly on polynomial RGs (e.g., Grammars 1, 2 and 7), and first-order RNNs perform poorly on proportional RGs (e.g., Grammars 5 and 6). In addition, for first-order RNNs, both their overall classification performance and misclassified strings indicate that these RNNs randomly choose some RGs to learn when learning proportional RGs. For exponential RGs (e.g., Grammar 3), we find that there exist some patterns in strings misclassified by certain first-order and gated RNNs. For example, LSTM tends to ignore "101" appearing at the end of a string and subsequently a has high false-positive errors (and learns some less deterministic transitions). In contrast, the SRN tends to lose count of consecutive 0 s or 1 s. These results indicate that these RNNs learn a smoothed boundary of the manifold that holds these strings. Since these common substrings are more likely to lie in the periphery of the manifold, it suggests the use of up-sampling to compensate for this problem.

Conclusions and Future Work
A theoretical analysis and empirical validation for subclasses of regular grammars is presented. Specifically, to measure the complexity of regular grammar, we introduced an entropy metric based on the concentric ring representation, which essentially reflects the difficulty in training RNNs to learn the grammar. Using entropy, we categorized regular grammar into three disjoint subclasses: polynomial class, exponential class and proportional class. In addition, we provided classification theorems for different representations of regular grammar. Given a regular grammar, these theorems use its corresponding properties in the given representation to efficiently determine which subclass a grammar belongs to without calculating the entropy value. Several common representations including deterministic finite automata, regular expression and sets have a corresponding case study which illustrates their applications. This categorization could also be applied to other relevant representations. Finally, we conducted an experiment to demonstrate the influence of grammar learning based on its complexity, which validates the effectiveness of the proposed entropy metric and the theoretical analysis. All RNNs have problems learning certain classes of grammars. It would seem the grammar chosen matters more than the RNN architecture. We believe this work provides a deeper understanding of the internal structure of regular grammar in the context of learning.
Future work could include an extension to other types of grammars, e.g., context-free grammars. The concentric ring representation is independent of grammar type and can be similarly applied to context-free grammars giving similar results to their entropy. However, classification differs dramatically. For instance, when we consider the parentheses grammar, the entropy can be obtained by the central binomial coefficient, which fails to fall in any of the classes proposed in this work. Another perspective is to study grammar learning in terms of recurrent models. Such a connection between DFA and RNNs can provide insights into explainable artificial intelligence and adversarial machine learning.