Reasoning about infinite computation paths
- 1 November 1983
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 185-194
- https://doi.org/10.1109/sfcs.1983.51
Abstract
We investigate extensions of temporal logic by finite automata on infinite words. There are three different types of acceptance conditions (finite, looping and repeating) that one can give for these finite automata. This gives rise to three different logics. It turns out, however. that these logics have the same expressive power but differ in the complexity of their decision problem. We also investigate the addition of alternation and show that it does not increase the complexity of the decision problem.Keywords
This publication has 21 references indexed in Scilit:
- Results on the propositional μ-calculusPublished by Springer Nature ,1982
- Succinct representation of regular languages by boolean automataTheoretical Computer Science, 1981
- AlternationJournal of the ACM, 1981
- Descriptively complete process logicActa Informatica, 1980
- A Calculus of Communicating SystemsLecture Notes in Computer Science, 1980
- The temporal logic of programsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1977
- Weak monadic second order theory of succesor is not elementary-recursiveLecture Notes in Mathematics, 1975
- Theories of automata on ω-tapes: A simplified approachJournal of Computer and System Sciences, 1974
- Testing and generating infinite sequences by a finite automatonInformation and Control, 1966
- Infinite sequences and finite machinesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1963