Algebraic and logical characterizations of deterministic linear time classes
From MaRDI portal
Publication:5048946
DOI10.1007/BFB0023481zbMATH Open1498.68119MaRDI QIDQ5048946FDOQ5048946
Authors: Thomas Schwentick 
Publication date: 9 November 2022
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
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
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- A new recursion-theoretic characterization of the polytime functions
- Title not available (Why is that?)
- A Natural NP-Complete Problem with a Nontrivial Lower Bound
- Title not available (Why is that?)
- Title not available (Why is that?)
- Satisfiability Is Quasilinear Complete in NQL
- Invariance properties of RAMs and linear time
- Sorting, linear time and the satisfiability problem
- ON THE NOTION OF LINEAR TIME COMPUTABILITY
- A Nontrivial Lower Bound for an NP Problem on Automata
- Linear Time Algorithms and NP-Complete Problems
- Title not available (Why is that?)
- An algebra and a logic for \(NC^ 1\)
- Tailoring recursion for complexity
- Title not available (Why is that?)
Cited In (6)
- Graph properties checkable in linear time in the number of vertices
- Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time
- All Linear-Time Congruences for Familiar Operators Part 2: Infinite LTSs
- Function-algebraic characterizations of log and polylog parallel time
- Title not available (Why is that?)
- Title not available (Why is that?)
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)
