Logic for Unambiguous Context-Free Languages
We give in this paper a logical characterization for unambiguous Context Free Languages, in the vein of descriptive
complexity. A fragment of the logic characterizing context free languages given by Lautemann, Schwentick and
Th´ erien based on implicit definability is used for this aim. We obtain a new connection between two undecidable
problems, a logical one and a language theoretical one.
J-M. Autebert, Th´ eorie des langages et des automates, 1994.
J-M. Autebert, Personnal communication, 1998.
J-M. Autebert, J. Berstel and L. Boasson, Context free languages and pushdown automata, in Handbook of formal languages vol 1, Springer Verlag 1996.
J. R. B ¨ uchi, Weak second-order arithmetic and finite automata, in Zeit.Math.Logik und Grund. Math. vol 6 (1960),
N. Chomsky and M. Sch ¨ utzenberger, The algebraic theory
of context free languages, in Computer Programming and
Formal Systems, 118-161, North Holland, 1963.
J. E. Doner, Tree acceptors and some of their applications,
in Journal of Computer and System Science 4, (1970), 406-451.
H. D. Ebbinghaus and J. Flum, Finite Model Theory,
T. Eiter, G. Gottlob and Y. Gurevich, Existential Secondorder Logic Over Strings, Proc. of the 13th Symp. of Logic In Computer Science 1998.
C. C. Elgot, Decision problems of finite automata design
an related arithmetics, Transactions of the American Mathematecal Society 98 (1961), 21-52.
R. Fagin, Generalized first–order spectra and polynomial
time recognizable sets, in RM Karp editor Complexity of
computation, SIAM-AMS Proceedings 1974.
F. G ´ ecseg and M. Steinby, Tree automata, in Handbook of
formal languages vol 3, Springer Verlag 1996.
M. A. Harrison, Introduction to formal language theory, Addison Wesley 1978.
G. Hotz, Normal form transformations of context-free languages, in Acta Cybernetica 4, (1978), 65-84.
P. Kolaitis, Implicit definability on finite structures and unambiguous computations, in Proc. 5th Symp. of logic in
computer science, 1990.
Zo´ e Lacroix, Bases de donn´ ees des relations implicites aux
relations contraintes, Ph.D. Universit ´ e de Paris Sud 1996.
C. Lautemann, T. Schwentick and D. Th´ erien, Logics for
context free languages, in C.S.L 95 lecture notes in computer science 205-216.
R. McNaughton and S. Papert, Counter free automata,
M.I.T. Press 1971.
J. Mezei and J. B. Wright, Algebraic automata and context
free sets., Information and Control, 1967.
J-E. Pin, Logic semigroups and automata on words, Annals
of Mathematics and Artificial Intelligence 16 (1996), 343-384.
H. Straubing, Finite Automata, Formal Logic, and Circuit
Complexity, Birkh ¨ auser, 1994.
J. W. Thatcher and J. B. Wright, Generalized finite automata with application to a decision problem of secondorder logic, in Mathematical System Theory 2 (1968) 57-82.
W. Thomas, Language automata and logic, in Handbook of
formal languages 3, Springer Verlag 1996.
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution 3.0 License.