Related Experiment Video
Updated: Jun 15, 2025
08:00
DNA Nanotubes as a Versatile Tool to Study Semiflexible Polymers
Published on: October 25, 2017
6.9K
On Polynomial Recursive Sequences
Michaël Cadilhac1, Filip Mazowiecki2, Charles Paperman3
1DePaul University, Chicago, IL 60484 USA.
Theory of Computing Systems
|August 26, 2024
Summary
We investigated polynomial recursive sequences, a nonlinear extension of linear ones. Our key finding is that the sequence n^2 is not polynomial recursive, impacting the study of nonlinear weighted automata.
Area of Science:
- Theoretical computer science
- Formal languages and automata theory
Background:
- Polynomial recursive sequences are a nonlinear extension of linear recursive sequences.
- These sequences are relevant to nonlinear weighted automata and class separations.
- A known example of a polynomial recursive sequence is n!
Purpose of the Study:
- To determine the expressive power of polynomial recursive sequences.
- To investigate the expressiveness of the sequence n^2 within this framework.
Main Methods:
- Analysis of the properties of polynomial recursive sequences.
- Demonstration of the non-expressiveness of n^2 using theoretical methods.
Main Results:
- The sequence n^2 is proven to not be polynomial recursive.
- This result contributes to understanding the limitations of polynomial recursive sequences.
Conclusions:
- The class of polynomial recursive sequences has limitations in expressive power.
- The findings have implications for the study of nonlinear weighted automata and their separations.
Related Concept Videos
01:16Basic Discrete Time Signals
201
The unit step sequence is defined as 1 for zero and positive values of the integer n. This sequence can be graphically displayed using a set of eight sample points, showing a step function starting from n=0 and remaining constant thereafter.
The unit impulse or sample sequence is mathematically expressed as zero for all n values except at n=0, where it is one. The unit impulse sequence, denoted by δ(n), is the first difference of the unit step sequence, while the unit step sequence u(n) is...
The unit impulse or sample sequence is mathematically expressed as zero for all n values except at n=0, where it is one. The unit impulse sequence, denoted by δ(n), is the first difference of the unit step sequence, while the unit step sequence u(n) is...
201
01:19Routh-Hurwitz Criterion II
204
In the application of the Routh-Hurwitz criterion, two specific scenarios can arise that complicate stability analysis.
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
204
01:15Determination of Pi Terms
263
The Buckingham Pi theorem is a valuable method in dimensional analysis, reducing complex relationships between variables into dimensionless terms. Relevant variables in analyzing the lift force on an airplane wing include lift force, air density, wing area, aircraft velocity, and air viscosity. Expressing each variable in terms of fundamental dimensions — mass, length, and time — provides a consistent foundation for constructing these dimensionless terms.
The theorem indicates that...
The theorem indicates that...
263
01:24Exponential Fourier series
186
In audio signal processing, the exponential Fourier series plays a crucial role in sound synthesis, allowing complex sounds to be broken down into simpler sinusoidal components. This decomposition process is fundamental in analyzing and reconstructing musical notes and other audio signals. The exponential Fourier series expresses periodic signals as the sum of complex exponentials at both positive and negative harmonic frequencies, providing a powerful tool for signal analysis.
Euler's identity...
Euler's identity...
186
01:17Trigonometric Fourier series
246
Fourier series is a foundational mathematical technique that decomposes periodic functions into an infinite series of sinusoidal harmonics. This method enables the representation of complex periodic signals as sums of simple sine and cosine functions, facilitating their analysis and interpretation in various fields, including signal processing, acoustics, and electrical engineering.
The trigonometric Fourier series specifically expresses a periodic function with a defined period T using sine...
The trigonometric Fourier series specifically expresses a periodic function with a defined period T using sine...
246
01:05Maxam-Gilbert Sequencing
11.1K
In the same year as the discovery of the Sanger sequencing method, another group of scientists, Allan Maxam and Walter Gilbert, demonstrated their chemical-cleavage method for DNA sequencing. The Maxam-Gilbert method relies on using different chemicals that can cleave the DNA sequence at specific sites, the separation of resulting DNA fragments of variable size using electrophoresis, and deciphering the DNA sequence from the resulting gel bands.
Challenges of the Maxam-Gilbert Method
The...
Challenges of the Maxam-Gilbert Method
The...
11.1K