Algebraic and logical characterizations of deterministic linear time classes

DOI10.1007/BFB0023481MaRDI QIDQ5048946zbMATH OpenFDO

Authors Thomas Schwentick

Publication date 9 November 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 1304315
• Linear temporal logic with non-transitive time, algorithms for decidability and verification of admissibility
• scientific article; zbMATH DE number 1231505
• scientific article; zbMATH DE number 1863168
• A first order logic for specification of timed algorithms: Basic properties and a decidable class
• Automata and temporal logic over arbitrary linear time
• An algebraic study of tense logics with linear time
• Publication:4934321
• Algorithmic properties of branching-time logics

Cites work

• scientific article; zbMATH DE number 4101157 (Why is no real title available?)
• scientific article; zbMATH DE number 176527 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• scientific article; zbMATH DE number 806743 (Why is no real title available?)
• scientific article; zbMATH DE number 806752 (Why is no real title available?)
• A Natural NP-Complete Problem with a Nontrivial Lower Bound
• A Nontrivial Lower Bound for an NP Problem on Automata
• A new recursion-theoretic characterization of the polytime functions
• An algebra and a logic for \(NC^ 1\)
• Invariance properties of RAMs and linear time
• Linear Time Algorithms and NP-Complete Problems
• ON THE NOTION OF LINEAR TIME COMPUTABILITY
• Satisfiability Is Quasilinear Complete in NQL
• Sorting, linear time and the satisfiability problem
• Tailoring recursion for complexity

Cited in

(6)

• Graph properties checkable in linear time in the number of vertices
• All Linear-Time Congruences for Familiar Operators Part 2: Infinite LTSs
• Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time
• Function-algebraic characterizations of log and polylog parallel time
• scientific article; zbMATH DE number 3872715 (Why is no real title available?)
• scientific article; zbMATH DE number 1863168 (Why is no real title available?)

This page was built for publication: Algebraic and logical characterizations of deterministic linear time classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5048946)