Algebraic and logical characterizations of deterministic linear time classes
From MaRDI portal
Recommendations
- A logical characterisation of linear time on nondeterministic Turing machines
- Linear temporal logic with non-transitive time, algorithms for decidability and verification of admissibility
- scientific article; zbMATH DE number 1231505
- An algebraic characterization of data and timed languages
- 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
- Decidable classes of the verification problem in a timed predicate logic
- Algorithmic properties of branching-time logics
Cites work
- A Natural NP-Complete Problem with a Nontrivial Lower Bound
- A new recursion-theoretic characterization of the polytime functions
- A Nontrivial Lower Bound for an NP Problem on Automata
- An algebra and a logic for \(NC^ 1\)
- scientific article; zbMATH DE number 4101157 (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?)
- 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
- The expressive power of second order Horn logic
Cited in
(8)- Function-algebraic characterizations of log and polylog parallel time
- All Linear-Time Congruences for Familiar Operators Part 2: Infinite LTSs
- scientific article; zbMATH DE number 3872715 (Why is no real title available?)
- ON THE NOTION OF LINEAR TIME COMPUTABILITY
- A conjunctive logical characterization of nondeterministic linear time
- Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time
- An algebraic characterization of data and timed languages
- Graph properties checkable in linear time in the number of vertices
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)