摘要: Descriptive Complexity [I98] is an approach to complexity that measures the richness of a language or sentence needed describe given property. There profound relationship between traditional computational problem and descriptive problem. In this setting, finite object being worked on treated as logical structure. Thus part model theory [EF95].
springer.com
core.ac.uk
sci-hub.st 参考文章(12)
Jörg Flum, Heinz-Dieter Ebbinghaus, Finite Model Theory ,(1995)
Sérgio Vale Aguiar Campos, Kenneth L. McMillan, Edmund M. Clarke, Vassili Hartonas-Garmhausen, Symbolic Model Checking ,(1993)
N. Immerman, DSPACE (n/sup k/)=VAR(k+1) structure in complexity theory annual conference. pp. 334- 340 ,(1991) , 10.1109/SCT.1991.160278
Robert P. Kurshan, Computer-Aided Verification of Coordinating Processes: The Automata-Theoretic Approach ,(1995)
Ramesh Bharadwaj, Constance Heitmeyer, Verifying SCR Requirements Specifications Using State Exploration ,(1997)
Neil Immerman, Moshe Y. Vardi, Model Checking and Transitive-Closure Logic computer aided verification. ,vol. 1254, pp. 291- 302 ,(1997) , 10.1007/3-540-63166-6_29
Neil Immerman, Languages that capture complexity classes SIAM Journal on Computing. ,vol. 16, pp. 760- 778 ,(1987) , 10.1137/0216051
R. P. Kurshan, Formal verification in a commercial setting design automation conference. pp. 258- 262 ,(1997) , 10.1145/266021.266089
J. Van Leeuwen, Handbook of theoretical computer science ,(1990)
E. Allen Emerson, Temporal and Modal Logic. Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B). pp. 995- 1072 ,(1990)