Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

Linear Circuits01:17

Linear Circuits

869
A linear circuit is characterized by its output having a direct proportionality to its input, adhering to the linearity property, which encompasses the principles of homogeneity (scaling) and additivity. Homogeneity dictates that when the input, also referred to as the excitation, is multiplied by a constant factor, the output, known as the response, is correspondingly scaled by the same constant factor. For instance, if the current is multiplied by a constant 'k,' the voltage likewise...
869
Linear Momentum00:55

Linear Momentum

18.1K
The term momentum is used in various ways in everyday language, most of which are consistent with the precise scientific definition. Generally, momentum implies a tendency to continue on course—to move in the same direction; we tend to speak of sports teams or politicians gaining and maintaining the momentum to win.  Momentum is also associated with great mass and speed and is often considered when talking about collisions. For example, when rugby players collide and fall to the...
18.1K
Linearization and Approximation01:26

Linearization and Approximation

57
Linearization is a mathematical technique used to approximate complex, nonlinear functions with simpler linear models in the vicinity of a chosen reference point. The method is based on the idea that, although a function may be difficult to evaluate exactly, its behavior near a specific input value can often be closely approximated by the tangent line at that point. This approach is particularly useful when small deviations from a known value are involved.Consider the square root function, for...
57
Application of Linearization and Approximation01:29

Application of Linearization and Approximation

88
A drone flying through complex terrain often relies on more than one sensing method to estimate small changes in altitude. Along with direct measurements, air pressure provides a useful indirect indicator of vertical movement. Atmospheric pressure decreases as altitude increases, and this relationship is commonly described using an exponential model. Although accurate, converting pressure measurements into altitude values requires calculations that are too complex to perform repeatedly during...
88
Linear Momentum in Control Volume01:13

Linear Momentum in Control Volume

1.3K
Newton's second law is applied to obtain the linear momentum in a control volume in a fluid system. According to this law, the rate of change of linear momentum is equal to the sum of external forces acting on the system. When a control volume matches the fluid system at a specific moment, the forces acting on both are identical. Reynolds transport theorem helps explain this by breaking down the system's linear momentum into two components: the rate of change of linear momentum within...
1.3K
Application of the Linear Momentum Equation01:15

Application of the Linear Momentum Equation

423
The application of the linear momentum equation can be used to analyze the forces needed to hold a 180-degree pipe bend in place with flowing water. In this case, water flows through the bend with a constant cross-sectional area of 0.01 square meters and a flow velocity of 15 meters per second. The pressure at the entrance is 0.2 Megapascals and the pressure at the exit is 0.16 Megapascals.
The goal is to determine the force components in the x and y directions to hold the pipe in place. Since...
423

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Comparison of general anesthesia versus no anesthesia in elective transjugular intrahepatic portosystemic shunt (TIPS): Procedural and hemodynamic parameters.

PloS one·2026
Same author

On the Parameterized Complexity of Eulerian Strong Component Arc Deletion.

Algorithmica·2025
Same author

Balloon enteroscopy-assisted endoscopic retrograde cholangiography and rendezvous procedures in patients with altered gastrointestinal anatomy.

Scandinavian journal of gastroenterology·2022
Same author

Microbial Degradation Rates of Natural Bitumen.

Environmental science & technology·2021
Same author

Circulating Microparticles Decrease After Cardiac Stress in Patients With Significant Coronary Artery Stenosis.

Clinical cardiology·2016
Same journal

Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity.

Algorithmica·2026
Same journal

A General Upper Bound for the Runtime of a Coevolutionary Algorithm on Impartial Combinatorial Games.

Algorithmica·2026
Same journal

Fully Characterizing Lossy Catalytic Computation.

Algorithmica·2026
Same journal

Parameterized Complexities of Dominating and Independent Set Reconfiguration.

Algorithmica·2026
Same journal

The SLO Hierarchy of Pseudo-Boolean Functions and Runtime of Evolutionary Algorithms.

Algorithmica·2026
Same journal

From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem.

Algorithmica·2025
See all related articles

Related Experiment Video

Updated: Jan 28, 2026

High-precision Electromagnetic Flowmeter with Empty Pipe Detection via Complex Programmable Logic Device-based Waveform Recognition
05:11

High-precision Electromagnetic Flowmeter with Empty Pipe Detection via Complex Programmable Logic Device-based Waveform Recognition

Published on: June 27, 2025

668

Backdoors for Linear Temporal Logic.

Arne Meier1, Sebastian Ordyniak2, M S Ramanujan3

  • 11Institut für Theoretische Informatik, Leibniz Universität Hannover, Appelstrasse 4, 30167 Hannover, Germany.

Algorithmica
|March 5, 2019
PubMed
Summary
This summary is machine-generated.

We introduce the backdoor set approach to temporal logic, analyzing its parameterized complexity for satisfiability. Detection is tractable, but evaluation complexity varies for Horn and Krom formulas.

Keywords:
Backdoor setsLinear temporal logicParameterized complexity

More Related Videos

Anteromesial Temporal Lobectomy for Medically Intractable Temporal Lobe Epilepsy: An Operative Study
11:29

Anteromesial Temporal Lobectomy for Medically Intractable Temporal Lobe Epilepsy: An Operative Study

Published on: August 15, 2025

2.2K
Linearization of the Bradford Protein Assay
06:35

Linearization of the Bradford Protein Assay

Published on: April 12, 2010

103.5K

Related Experiment Videos

Last Updated: Jan 28, 2026

High-precision Electromagnetic Flowmeter with Empty Pipe Detection via Complex Programmable Logic Device-based Waveform Recognition
05:11

High-precision Electromagnetic Flowmeter with Empty Pipe Detection via Complex Programmable Logic Device-based Waveform Recognition

Published on: June 27, 2025

668
Anteromesial Temporal Lobectomy for Medically Intractable Temporal Lobe Epilepsy: An Operative Study
11:29

Anteromesial Temporal Lobectomy for Medically Intractable Temporal Lobe Epilepsy: An Operative Study

Published on: August 15, 2025

2.2K
Linearization of the Bradford Protein Assay
06:35

Linearization of the Bradford Protein Assay

Published on: April 12, 2010

103.5K

Area of Science:

  • Computer Science
  • Theoretical Computer Science
  • Logic in Computer Science

Background:

  • Temporal logic is crucial for reasoning about time-dependent systems.
  • Satisfiability problems in temporal logic can be computationally complex.
  • Parameterized complexity offers a finer-grained analysis of computational problems.

Purpose of the Study:

  • To introduce the backdoor set approach to the global fragment of linear temporal logic.
  • To analyze the parameterized complexity of satisfiability problems concerning backdoor size.
  • To differentiate the complexity of backdoor detection versus evaluation for Horn and Krom formulas.

Main Methods:

  • Application of the backdoor set methodology to temporal logic satisfiability.
  • Parameterized complexity analysis, focusing on backdoor size as the parameter.
  • Classification of operator fragments for past, future, and always temporal operators.

Main Results:

  • Backdoor detection is proven to be fixed-parameter tractable.
  • Evaluation complexity differs: paraNP-complete for Krom formulas.
  • For Horn formulas, evaluation is either fixed-parameter tractable or paraNP-complete, contingent on the operator fragment.

Conclusions:

  • The backdoor set approach provides a valuable lens for understanding temporal logic satisfiability.
  • Parameterized complexity reveals distinct computational challenges for detection and evaluation.
  • The specific structure of temporal operators significantly impacts the complexity of evaluating backdoors in Horn and Krom fragments.