Arrow Research search

Author name cluster

Sheng Yu

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

32 papers
2 author rows

Possible papers

32

AAAI Conference 2026 Conference Paper

GraphGrasp: Lightweight and Efficient Graph-Guided 6-DoF Robotic Grasp Pose Estimation Network

  • Sheng Yu
  • Di-Hua Zhai
  • Yuanqing Xia

6-DoF object grasping is a crucial skill for embodied intelligent robots. Previous methods often rely on large-scale networks for feature extraction, followed by grasp pose prediction, which increases the network's parameter count and overlooks the geometric and graph features of the point cloud. To address these challenges, we propose GraphGrasp, a graph-guided 6-DoF grasping pose prediction method. It performs graph analysis from the perspectives of scene, object, and grasping graphs. First, we introduce a graph feature embedding method based on local-global features to model the scene graph effectively. Then, we use a graph transformer strategy to represent spatial relationships between objects in the object graph. Finally, we propose a multi-metric, multi-level grasp pose evaluation algorithm to predict and explore graspable points, enabling effective construction of grasp graphs and accurate grasp pose evaluation. We test GraphGrasp on the GraspNet-1Billion dataset, and the results show that, compared to previous methods, it achieves nearly the same performance with about 1/5 of the parameters of state-of-the-art methods, significantly improving grasp pose prediction speed. Additionally, in real-world robot grasping scenarios, GraphGrasp outperforms previous methods in practical grasp pose prediction tasks.

AAAI Conference 2026 Conference Paper

LLM-Aligned Geographic Item Tokenization for Local-Life Recommendation

  • Hao Jiang
  • Guoquan Wang
  • Donglin Zhou
  • Sheng Yu
  • Yang Zeng
  • Wencong Zeng
  • Kun Gai
  • Guorui Zhou

Recent advances in Large Language Models (LLMs) have enhanced text-based recommendation by enriching traditional ID-based methods with semantic generalization capabilities. Text-based methods typically encode item textual information via prompt design and generate discrete semantic IDs through item tokenization. However, in domain-specific tasks such as local-life services, simply injecting location information into prompts fails to capture fine-grained spatial characteristics and real-world distance awareness among items. To address this, we propose LGSID, an LLM-Aligned Geographic Item Tokenization Framework for Local-life Recommendation. This framework consists of two key components: (1) RL-based Geographic LLM Alignment, and (2) Hierarchical Geographic Item Tokenization. In the RL-based alignment module, we initially train a list-wise reward model to capture real-world spatial relationships among items. We then introduce a novel G-DPO algorithm that uses pre-trained reward model to inject generalized spatial knowledge and collaborative signals into LLMs while preserving their semantic understanding. Furthermore, we propose a hierarchical geographic item tokenization strategy, where primary tokens are derived from discrete spatial and content attributes, and residual tokens are refined using the aligned LLM’s geographic representation vectors. Extensive experiments on real-world Kuaishou industry datasets show that LGSID consistently outperforms state-of-the-art discriminative and generative recommendation models. Ablation studies, visualizations, and case studies further validate its effectiveness.

AAAI Conference 2025 Conference Paper

KeyPose: Category-Level 6D Object Pose Estimation with Self-Adaptive Keypoints

  • Sheng Yu
  • Di-Hua Zhai
  • Yuanqing Xia

Category-level object pose estimation is an important task in computer vision. Some prior methods based on assumptions often struggle with drastic changes in object appearance. To address this challenge, we propose a new method for object pose estimation based on object-adaptive keypoints. In this paper, we first introduce a transformer-based keypoint prediction method for adaptive forecasting of point cloud keypoints. This method calculates the similarity between keypoint features and point cloud features, allowing keypoints to represent object geometry more effectively. Furthermore, to enhance the geometric feature construction of keypoints, we propose a graph-based keypoint feature aggregation method, which considers both the structural relationships between keypoints and the point cloud, strengthening the network's understanding of geometric structures. At this stage, keypoints remain at the geometric spatial level of the object and have not been predicted in NOCS. To improve the accuracy of keypoint prediction in NOCS, we design a NOCS voxelization method that divides NOCS into multiple voxels and accurately predicts NOCS keypoints within these voxels. Experimental results on multiple benchmark datasets demonstrate that our proposed KeyPose method outperforms all existing methods, achieving over 20% improvement in pose accuracy on some critical datasets.

ICRA Conference 2025 Conference Paper

Rapid Dynamic Obstacle Avoidance for UAVs Enhanced by DVS and Neuromorphic Computing

  • Siyang Wang
  • Sheng Yu
  • Tingbang Liang
  • Yilin Shi
  • Yongqiang Ma
  • Pengju Ren

Achieving rapid and accurate dynamic obstacle avoidance is crucial for enhancing the survivability of unmanned aerial vehicles (UAVs) in hazardous conditions. To accomplish dynamic obstacle avoidance, sensors with high temporal resolution and efficient processing models are required. Dynamic vision sensors (DVS) fulfill the sensing requirements, while spiking neural networks (SNNs) address the processing demands. In this paper, we develop an end-to-end obstacle avoidance algorithm for UAVs using only a single monocular DVS as the sensor and further enhance accuracy and speed through our proposed mechanisms. The algorithm consists of three components: ego-motion compensation, an SNN model for movement analysis, and a force filter inspired by spiking neurons. In movement analysis, we propose the temporal potential pooling (TPP) and incremental event (EI) mechanisms to accelerate our SNN model. The real-flight experiments confirm that our algorithm achieves approximately 90% accuracy with a processing latency as low as 4ms on a GPU, surpassing state-of-the-art methods. Ablation studies show that the proposed method maintains high accuracy in movement detection while significantly reducing computational time. Our method operates in real-time, achieves high accuracy, and is feasible across a wide range of environments. Our code is available at https://github.com/AmperiaWang/oanet_s1 for reproducibility.

AAAI Conference 2024 Conference Paper

CatFormer: Category-Level 6D Object Pose Estimation with Transformer

  • Sheng Yu
  • Di-Hua Zhai
  • Yuanqing Xia

Although there has been significant progress in category-level object pose estimation in recent years, there is still considerable room for improvement. In this paper, we propose a novel transformer-based category-level 6D pose estimation method called CatFormer to enhance the accuracy pose estimation. CatFormer comprises three main parts: a coarse deformation part, a fine deformation part, and a recurrent refinement part. In the coarse and fine deformation sections, we introduce a transformer-based deformation module that performs point cloud deformation and completion in the feature space. Additionally, after each deformation, we incorporate a transformer-based graph module to adjust fused features and establish geometric and topological relationships between points based on these features. Furthermore, we present an end-to-end recurrent refinement module that enables the prior point cloud to deform multiple times according to real scene features. We evaluate CatFormer's performance by training and testing it on CAMERA25 and REAL275 datasets. Experimental results demonstrate that CatFormer surpasses state-of-the-art methods. Moreover, we extend the usage of CatFormer to instance-level object pose estimation on the LINEMOD dataset, as well as object pose estimation in real-world scenarios. The experimental results validate the effectiveness and generalization capabilities of CatFormer. Our code and the supplemental materials are avaliable at https://github.com/BIT-robot-group/CatFormer.

AIIM Journal 2024 Journal Article

Efficient symptom inquiring and diagnosis via adaptive alignment of reinforcement learning and classification

  • Hongyi Yuan
  • Sheng Yu

Medical automatic diagnosis aims to organize real-world diagnostic processes similar to those from human doctors and to achieve accurate diagnoses by interacting with patients. The task is formulated as a sequential decision-making problem with a series of information inquiry steps (asking about symptoms and ordering examinations) and the final diagnosis. Recent research has studied incorporating reinforcement learning for information inquiry and classification techniques for disease diagnosis, respectively. However, studies on efficiently and effectively combining the two procedures are still lacking. To address this issue, we devised an adaptive mechanism to align reinforcement learning and classification methods using distribution entropy as the medium. Additionally, we created a new dataset for patient simulation to address the lack of large-scale evaluation benchmarks. The dataset is extracted from the MedlinePlus knowledge base and contains significantly more diseases and more comprehensive symptom and examination information than existing datasets. Experimental evaluation shows that our method outperforms three current state-of-the-art methods on different datasets by achieving higher medical diagnostic accuracy with fewer inquiring turns.

TMLR Journal 2024 Journal Article

EHRDiff: Exploring Realistic EHR Synthesis with Diffusion Models

  • Hongyi Yuan
  • Songchi Zhou
  • Sheng Yu

Electronic health records (EHR) contain a wealth of biomedical information, serving as valuable resources for the development of precision medicine systems. However, privacy concerns have resulted in limited access to high-quality and large-scale EHR data for researchers, impeding progress in methodological development. Recent research has delved into synthesizing realistic EHR data through generative modeling techniques, where a majority of proposed methods relied on generative adversarial networks (GAN) and their variants for EHR synthesis. Despite GAN-based methods attaining state-of-the-art performance in generating EHR data, these approaches are difficult to train and prone to mode collapse. Recently introduced in generative modeling, diffusion models have established cutting-edge performance in image generation, but their efficacy in EHR data synthesis remains largely unexplored. In this study, we investigate the potential of diffusion models for EHR data synthesis and introduce a novel method, EHRDiff. Through extensive experiments, EHRDiff establishes new state-of-the-art quality for synthetic EHR data, protecting private information in the meanwhile.

TCS Journal 2013 Journal Article

Online scheduling of simple linear deteriorating jobs to minimize the total general completion time

  • Sheng Yu
  • Prudence W.H. Wong

Traditional scheduling assumes that the processing time of a job is fixed. Yet there are numerous situations in which the processing time increases (deteriorates) as the start time increases. In particular, lots of work has been devoted to jobs with simple linear deterioration. The processing time p j of job J j is a simple linear function of its start time s j, precisely, p j = b j s j, where b j is the deteriorating rate. In this paper, we study the problem of online non-preemptive scheduling of jobs with arbitrary release times and simple linear deteriorating rates on a single machine to minimize the total general completion time. We present an algorithm DSDR (Delayed Smallest Deteriorating Rate) and prove that it achieves the best-possible competitive ratio ( 1 + b max ) α for all deterministic online algorithms, where α is the general index of completion time and α > 0.

TCS Journal 2012 Journal Article

State complexity of combined operations with two basic operations

  • Bo Cui
  • Yuan Gao
  • Lila Kari
  • Sheng Yu

This paper studies the state complexity of ( L 1 L 2 ) R, L 1 R L 2, L 1 ∗ L 2, ( L 1 ∪ L 2 ) L 3, ( L 1 ∩ L 2 ) L 3, L 1 L 2 ∩ L 3, and L 1 L 2 ∪ L 3 for regular languages L 1, L 2, and L 3. We first show that the upper bound proposed by Liu et al. (2008) [18] for the state complexity of ( L 1 L 2 ) R coincides with the lower bound and is thus the state complexity of this combined operation by providing some witness DFAs. Also, we show that, unlike most other cases, due to the structural properties of the result of the first operation of the combinations L 1 R L 2, L 1 ∗ L 2, and ( L 1 ∪ L 2 ) L 3, the state complexity of each of these combined operations is close to the mathematical composition of the state complexities of the component operations. Moreover, we show that the state complexities of ( L 1 ∩ L 2 ) L 3, L 1 L 2 ∩ L 3, and L 1 L 2 ∪ L 3 are exactly equal to the mathematical compositions of the state complexities of their component operations in the general cases. We also include a brief survey that summarizes all state complexity results for combined operations with two basic operations.

TCS Journal 2012 Journal Article

State complexity of union and intersection of square and reversal on k regular languages

  • Yuan Gao
  • Lila Kari
  • Sheng Yu

In this paper, we continue our study on the state complexity of combined operations on regular languages. We study the state complexities of ⋃ i = 1 k L i 2, ⋂ i = 1 k L i 2, ⋃ i = 1 k L i R, and ⋂ i = 1 k L i R, for regular languages L i, 1 ≤ i ≤ k, k ≥ 2. We obtain the exact bounds for these combined operations and show that the state complexities of ⋃ i = 1 k L i 2 and ⋂ i = 1 k L i 2 are the same as the mathematical compositions of the state complexities of their component individual operations, while, on the other hand, the state complexities of ⋃ i = 1 k L i R and ⋂ i = 1 k L i R are lower than the corresponding mathematical compositions.

TCS Journal 2012 Journal Article

State complexity of union and intersection of star on regular languages

  • Yuan Gao
  • Lila Kari
  • Sheng Yu

In this paper, we continue our study on state complexity of combined operations. We study the state complexities of L 1 ∗ ∪ L 2 ∗, ⋃ i = 1 k L i ∗, L 1 ∗ ∩ L 2 ∗, and ⋂ i = 1 k L i ∗ for regular languages L i, 1 ≤ i ≤ k. We obtain the exact bounds for these combined operations and show that the bounds are different from the mathematical compositions of the state complexities of their component individual operations.

TCS Journal 2009 Journal Article

Deciding determinism of caterpillar expressions

  • Kai Salomaa
  • Sheng Yu
  • Jinfeng Zan

Caterpillar expressions have been introduced by Brüggemann-Klein and Wood for applications in markup languages. Caterpillar expressions provide a convenient formalism for specifying the operation of tree-walking automata on unranked trees. Here we give a formal definition of determinism of caterpillar expressions that is based on the language of instruction sequences defined by the expression. We show that determinism of caterpillar expressions can be decided in polynomial time.

TCS Journal 2009 Journal Article

Estimation of state complexity of combined operations

  • Zoltán Ésik
  • Yuan Gao
  • Guangwu Liu
  • Sheng Yu

It appears that the state complexity of each combined operation has its own special features. Thus, it is important and practical to obtain good estimates for some commonly used general cases. In this paper, we consider the state complexity of combined Boolean operations and give an exact bound for all of them in the case when the alphabet is not fixed. Moreover, we show that for any fixed alphabet, this bound can be reached in infinitely many cases. We also consider the state complexity of multiple catenations. The state complexities are obtained in the cases of the catenations of three and four languages. An estimate for the catenation of an arbitrary number of languages is given, which is very close to the state complexities in the three and four languages cases.

TCS Journal 2009 Journal Article

Hierarchy and equivalence of multi-letter quantum finite automata

  • Daowen Qiu
  • Sheng Yu

Multi-letter quantum finite automata (QFAs) are a new one-way QFA model proposed recently by Belovs, Rosmanis, and Smotrovs [A. Belovs, A. Rosmanis, J. Smotrovs, Multi-letter reversible and quantum finite automata, in: Proceedings of the 13th International Conference on Developments in Language Theory, DLT’2007, Harrachov, Czech Republic, in: Lecture Notes in Computer Science, vol. 4588, Springer, Berlin, 2007, pp. 60–71], and they showed that multi-letter QFAs can accept with no error some regular languages ( ( a + b ) ∗ b ) that are unacceptable by the one-way QFAs. In this paper, we continue to study multi-letter QFAs. We mainly focus on two issues: (1) we show that ( k + 1 ) -letter QFAs are computationally more powerful than k -letter QFAs, that is, ( k + 1 ) -letter QFAs can accept some regular languages that are unacceptable by any k -letter QFA. A comparison with the one-way QFAs is made by some examples; (2) we prove that a k 1 -letter QFA A 1 and another k 2 -letter QFA A 2 are equivalent, if and only if, they are ( n 1 + n 2 ) 4 + k − 1 -equivalent, and the time complexity of determining the equivalence of two multi-letter QFAs using this method is O ( n 12 + k 2 n 4 + k n 8 ), where n 1 and n 2 are the numbers of states of A 1 and A 2, respectively, and k = max ( k 1, k 2 ). Some other issues are addressed for further consideration.

I&C Journal 2009 Journal Article

Variants of codes and indecomposable languages

  • Arto Salomaa
  • Kai Salomaa
  • Sheng Yu

We continue the investigation of representing a language as a catenation of languages, each of which cannot be further decomposed in a nontrivial fashion. We study such prime decompositions, both finite and infinite ones. The notion of a length code, an extension of the notion of a code leads to general results concerning decompositions of star languages. Special emphasis is on the decomposition of regular languages. Also some open problems are mentioned.

I&C Journal 2008 Journal Article

State complexity of basic language operations combined with reversal

  • Guangwu Liu
  • Carlos Martin-Vide
  • Arto Salomaa
  • Sheng Yu

We study the state complexity of combined operations on regular languages. Each of the combined operations is a basic operation combined with reversal. We show that their state complexities are all very different from the compositions of state complexities of individual operations.

TCS Journal 2007 Journal Article

On the existence of prime decompositions

  • Yo-Sub Han
  • Arto Salomaa
  • Kai Salomaa
  • Derick Wood
  • Sheng Yu

We investigate factorizations of regular languages in terms of prime languages. A language is said to be strongly prime decomposable if any way of factorizing it yields a prime decomposition in a finite number of steps. We give a characterization of the strongly prime decomposable regular languages and using the characterization we show that every regular language over a unary alphabet has a prime decomposition. We show that there exist non-regular unary languages that do not have prime decompositions. We also consider infinite factorizations of unary languages.

TCS Journal 2007 Journal Article

State complexity of combined operations

  • Arto Salomaa
  • Kai Salomaa
  • Sheng Yu

We study the state complexity of combined operations. Two particular combined operations are studied: star of union and star of intersection. It is shown that the state complexity of a combined operation is not necessarily similar to the combination of the individual state complexities of the participating operations.

I&C Journal 2006 Journal Article

Subword conditions and subword histories

  • Arto Salomaa
  • Sheng Yu

This paper introduces the notion of a subword condition and investigates languages defined by them. The special case, where the language reduces to one word, concerns the inference of a sequence from its subsequences. We obtain various characterization and decidability results for languages defined by subword conditions. The results contribute to the theory of Parikh matrices and arithmetizing the study of words. An important notion from early automata theory, that of a quasi-uniform event, plays a central role in our characterization.

TCS Journal 2005 Journal Article

Mergible states in large NFA

  • Cezar Câmpeanu
  • Nicolae Sântean
  • Sheng Yu

Quite often, trivial problems stated for deterministic finite automata (DFA) are surprisingly difficult for the non-deterministic case (NFA). In any non-minimal DFA for a given regular language, we can find two equivalent states which can be “merged” without changing the accepted language. This is not the case for NFA, where we can have non-minimal automata with no “mergible” states. In this paper, we prove a very basic result for NFA, that for a given regular language, any NFA of size greater than a computable constant must contain mergible states. Even more, we parameterized this constant in order to guarantee groups of an arbitrary number of mergible states.

TCS Journal 2004 Journal Article

On the state complexity of reversals of regular languages

  • Arto Salomaa
  • Derick Wood
  • Sheng Yu

We compare the number of states between minimal deterministic finite automata accepting a regular language and its reversal (mirror image). In the worst case the state complexity of the reversal is 2 n for an n-state language. We present several classes of languages where this maximal blow-up is actually achieved and study the conditions for it. In the case of finite languages the maximal blow-up is not possible but still a surprising variety of different growth types can be exhibited.

I&C Journal 2003 Journal Article

Follow automata

  • Lucian Ilie
  • Sheng Yu

We give two new algorithms for constructing small nondeterministic finite automata (NFA) from regular expressions. The first constructs NFAs with ε-transitions (εNFA) which are smaller than all the other εNFAs obtained by similar constructions. Their size is at most 3 2 |α|+ 5 2, where α is the regular expression. This is very close to optimal since we prove also the lower bound 4 3 |α|+ 5 2. The second constructs NFAs. It uses ε-elimination in the εNFAs we just introduced and builds a quotient of the well-known position automaton w. r. t. the equivalence given by the follow relation; therefore giving the name of follow automaton. The new automaton uses optimally the information from the positions of a regular expression. We compare the follow automaton with the best constructions to date and show that it has important advantages over those.

TCS Journal 2003 Journal Article

Reducing NFAs by invariant equivalences

  • Lucian Ilie
  • Sheng Yu

We give new general methods for constructing small non-deterministic finite automata (NFA) from arbitrary ones. Given an NFA, we compute the largest right-invariant equivalence on the set of states and then merge the equivalent states to obtain a smaller automaton. When applying this method to position automata, we get a way to convert regular expressions into NFAs which are always smaller than or equal to the position, partial derivative, and follow automata; it can be arbitrarily smaller. The construction can be dually made for left-invariant equivalences and then the two can be combined for even better results.

TCS Journal 2002 Journal Article

Decidability of EDT0L structural equivalence

  • Kai Salomaa
  • Sheng Yu

We show that a tree pushdown automaton can verify, for an arbitrary nondeterministically constructed structure tree t, that t does not correspond to any valid derivation of a given EDT0L grammar. In this way we reduce the structural equivalence problem for EDT0L grammars to deciding emptiness of the tree language recognized by a tree pushdown automaton, i. e. , to the emptiness problem for context-free tree languages. Thus we establish that structural equivalence for EDT0L grammars can be decided effectively. The result contrasts the known undecidability result for ET0L structural equivalence.

TCS Journal 2000 Journal Article

Alternating finite automata and star-free languages

  • Kai Salomaa
  • Sheng Yu

For a given extended regular expression e we construct an equational representation of an alternating finite automaton accepting the language denoted by e. For star-free extended regular expressions the construction yields a loop-free alternating finite automaton. Also the inclusion in the opposite direction holds and, thus, we obtain a new characterization for the class of star-free languages.

TCS Journal 1998 Journal Article

Synchronization expressions with extended join operation

  • Kai Salomaa
  • Sheng Yu

Synchronization expressions are high level constructs used for specifying minimal synchronization constraints of parallel processes. Their semantics is defined by the corresponding synchronization language. The original definition of synchronization expressions [12, 13] forces the languages to be closed under rewriting rules that, for instance, do not preserve regularity. Here we propose an extension of the syntactic definition of synchronization expressions, and an appropriate modification of their semantics. The extended definition has the advantage that it allows us to eliminate the less well motivated transformations (rewriting rules) describing properties of synchronization languages. We show that the modified rewriting rules preserve regularity of the languages. Also, we obtain a characterization of finite synchronization languages as the family consisting of languages satisfying the start-termination property and closed under three types of simple rewriting rules.

TCS Journal 1994 Journal Article

The state complexities of some basic operations on regular languages

  • Sheng Yu
  • Qingyu Zhuang
  • Kai Salomaa

We consider the state complexities of some basic operations on regular languages. We show that the number of states that is sufficient and necessary in the worst case for a deterministic finite automaton (DFA) to accept the catenation of an m-state DFA language and an n-state DFA language is exactly m2 n − 2 n − 1, for m, n ⩾ 1. The result of 2 n − 1 + 2 n − 2 states is obtained for the star of an n-state DFA language, n1. State complexities for other basic operations and for regular languages over a one-letter alphabet are also studied.

TCS Journal 1991 Journal Article

Decidability of structural equivalence of E0L grammars

  • Kai Salomaa
  • Sheng Yu

We introduce height-counting tree automata that are able to recognize the syntax trees of E0L grammars. The equivalence problem of height-counting tree automata is shown to be decidable and using this result we solve an open problem raised by Ottmann and Wood [5, 6], i. e. , the decidability of structural equivalence of E0L grammars.

TCS Journal 1986 Journal Article

On a public-key cryptosystem based on iterated morphisms and substitutions

  • Arto Salomaa
  • Sheng Yu

A public-key cryptosystem based essentially on ideas coming from L systems was introduced in (Salomaa and Welzl, 1983), see also (Salomaa, 1985) and (Salomaa, 1984). The system was further investigated in (Baunwall, Bertelsen and Weibel, 1986) and (Koskinen and Salomaa, 1985). The purpose of the present paper is to study the system, both from mathematical and cryptanalytic point of view. In particular, we investigate cryptanalytic approaches and what one can accomplish by preprocessing. We also discuss the desirable properties of the underlying DT0L system such as different types of backward determinism and the role of growth. The system is very flexible in many respects, for instance, as regards the plaintext blocksize.

TCS Journal 1986 Journal Article

Real-time, pseudo real-time, and linear-time ITA

  • Karel Culik
  • Sheng Yu

A k-ary iterative tree automaton (k-ary ITA) is a potentially infinite synchronous network of finite automata structured as k-ary tree with serial input and output at the root of the tree. The computational power of an ITA in real-time, pseudo real-time and linear-time is compared. The pseudo real-time is a new notion and means that every cell of an ITA makes a fixed number of computational steps for each input symbol. It is shown that every linear-time ITA can be simulated either by a pseudo real-time ITA of the same arity or by a real-time ITA of a higher arity. As an example, an ITA implementation of real-time infinite memory is described.

TCS Journal 1984 Journal Article

Iterative tree automata

  • Karel Culik
  • Sheng Yu

The iterative tree automaton is introduced as a binary tree-connected network with sequential input and output at the root of the tree. The real and linear time computational power of this type of systolic system as a language acceptor is studied. It is shown that for real-time computations the arity of the tree is essential while this is not the case for linear-time computations. Our main result is that every T(n)-time nondeterministic Turing machine can be simulated by an ITA in (deterministic) cT(n)-time. A number of properties of real-and linear-time ITA are proved.

v2026.09.13