Logics for context-free languages

被引：0
作者：
Lautemann, C
Schwentick, T
Therien, D
机构：
[1] MCGILL UNIV,MONTREAL,PQ,CANADA
[2] UNIV POLITECN CATALUNYA,E-08028 BARCELONA,SPAIN
来源：
COMPUTER SCIENCE LOGIC | 1995年 / 933卷
关键词：
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We define matchings, and show that they capture the essence of context-freeness. More precisely, we show that the class of context-free languages coincides with the class of those sets of strings which call be defined by sentences of the form There Exists b phi, where phi is first order, b is a binary predicate symbol, and the range of the second order quantifier is restricted to the class of matchings. Several variations and extensions are discussed.
引用
收藏
页码：205 / 216
页数：12
相关论文
共 13 条
  • [1] REACHABILITY IS HARDER FOR DIRECTED THAN FOR UNDIRECTED FINITE GRAPHS
    AJTAI, M
    FAGIN, R
    [J]. JOURNAL OF SYMBOLIC LOGIC, 1990, 55 (01) : 113 - 150
  • [2] BARRINGTON DAM, 1992, J COMPUT SYST SCI, V44, P478, DOI 10.1016/0022-0000(92)90014-A
  • [3] 2ND-ORDER AND INDUCTIVE DEFINABILITY ON FINITE STRUCTURES
    DEROUGEMONT, M
    [J]. ZEITSCHRIFT FUR MATHEMATISCHE LOGIK UND GRUNDLAGEN DER MATHEMATIK, 1987, 33 (01): : 47 - 63
  • [4] Doner J.E., 1970, J COMPUT SYST SCI, V4, P406
  • [5] Fagin R., 1993, Proceedings of the Eighth Annual Structure in Complexity Theory Conference (Cat. No.93CH3281-3), P19, DOI 10.1109/SCT.1993.336544
  • [6] FAGIN R, 1975, Z MATH LOGIK, V21, P89, DOI 10.1002/malq.19750210112
  • [7] Gecseg F., 1984, TREE AUTOMATA
  • [8] J. R. Buchi, 1960, Z MATH LOG GRUNDL MA, V6, P66
  • [9] ALGEBRAIC AUTOMATA AND CONTEXT-FREE SETS
    MEZEI, J
    WRIGHT, JB
    [J]. INFORMATION AND CONTROL, 1967, 11 (1-2): : 3 - &
  • [10] SALOMAA A, 1987, FORMAL LANGUAGES
12