Logic for Unambiguous Context-Free Languages

Yassine Hachaïchi


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.

Full Text:



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,

Springer 1995.

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.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.