NDLI: On the expressive power of variable-confined logics

Content Provider	IEEE Xplore Digital Library
Author	Kolaitis, P.G. Vardi, M.Y.
Copyright Year	1996
Description	Author affiliation: Dept. of Comput. Sci., California Univ., Santa Cruz, CA, USA (Kolaitis, P.G.)
Abstract	In this paper we study the comparative expressive power of variable-confined logics, that is, logics with a fixed finite number of variables. This is motivated by the fact that the number of variables is considered a logical resource in descriptive complexity theory. We consider the expressive power of the logics FO/sup k/ (first-order logic with k variables), LFP/sup k/ (LFP with k variables, appropriately defined), and /spl Lscr//sub /spl infin/w//sup k/ (infinitary logic with k variables) over classes of finite structures. While the definitions of FO/sup k/ and /spl Lscr//sub /spl infin/w//sup k/ are quite clear, it turns out that ramifying LFP is a more delicate matter. We define LFP/sup k/ in terms of systems of least fixpoints, i.e., instead of taking the least fixpoint of a single positive first-order formula, we consider simultaneous least fixpoints of a vector of positive first-order formulas. As evidence that LFP/sup k/, k/spl ges/1, is the right ramification of LFP we offer two main results. The first is a new proof of a theorem by A. Dawar et al. (1995) to the effect that equivalence classes of finite structures with respect to the logic /spl Lscr//sub /spl infin/w//sup k/ are expressible in FO/sup k/. The second result, novel and technically difficult, is a characterization for each k/spl ges/1 of the collapse of /spl Lscr//sub /spl infin/w//sup k/ to FO/sup k/ in terms of boundedness of LFP/sup k/. More precisely, we establish the following stronger version of McColm's second conjecture: /spl Lscr//sub /spl infin/w//sup k/=FO/sup k/ on a class C of finite structures if and only if LFP/sup k/ is uniformly bounded on C.
Starting Page	348
Ending Page	359
File Size	1176743
Page Count	12
File Format	PDF
ISBN	0818674636
ISSN	10436871
DOI	10.1109/LICS.1996.561446
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1996-07-27
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Logic Computer science Complexity theory Uniform resource locators
Content Type	Text
Resource Type	Article
Subject	Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Logic, complexity, and games

Relating word and tree automata

Using temporal logics for planning and control

Linear vs. branching time: a complexity-theoretic perspective

Complexity and expressive power of logic programming

Hard sets are hard to find

On the expressive power of simply typed and let-polymorphic lambda calculi

On the proof complexity of logics of bounded branching

Inflationary fixed points in modal logic

On the expressive power of variable-confined logics

Similar Documents

Logic, complexity, and games

Relating word and tree automata

Using temporal logics for planning and control

Linear vs. branching time: a complexity-theoretic perspective

Complexity and expressive power of logic programming

Hard sets are hard to find

On the expressive power of simply typed and let-polymorphic lambda calculi

On the proof complexity of logics of bounded branching

Inflationary fixed points in modal logic

On the expressive power of variable-confined logics