Article One help-bit doesn't help Share on Authors: Richard Beigel Lehigh University, Elect Eng Comp Science, 19 Memorial Dr W Ste 2, Bethlehem PA Lehigh University, Elect Eng Comp Science, 19 Memorial Dr W Ste 2, Bethlehem PAView Profile , Tirza Hirst Bar-llan University, Department of Mathematics and Computer Science, Bar-Ilan University, 52900 Ramat-Gan, Israel Bar-llan University, Department of Mathematics and Computer Science, Bar-Ilan University, 52900 Ramat-Gan, IsraelView Profile Authors Info & Claims STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computingMay 1998 Pages 124–130https://doi.org/10.1145/276698.276720Online:23 May 1998Publication History 6citation229DownloadsMetricsTotal Citations6Total Downloads229Last 12 Months4Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

This paper continues our work on infinite, recursive structures. We investigate the descriptive complexity of several logics over recursive structures, including first-order, second-order, and fixpoint logic, exhibiting connections between expressibility of a property and its computational complexity. We then address 0-1 laws, proposing a version that applies to recursive structures and using it to prove several non-expressibility results.

This is the second in a series of papers on the inherent power of bounded cooperative concurrency, whereby an automaton can be in some bounded number of states that cooperate in accepting the input. In this paper, we consider pushdown automata. We are interested in differences in power of expression and in exponential (or higher) discrepancies in succinctness between variants of pda's that incorporate nondeterminism (E), pure parallelism (A), and bounded cooperative concurrency (C). Technically, the results are proved for cooperating push-down automata with cooperating states, but they hold for appropriate versions of most concurrent models of computation. We exhibit exhaustive sets of upper and lower bounds on the relative succinctness of these features for three classes of languages: deterministic context-free, regular, and finite. For example, we show that C represents exponential savings in succinctness in all cases except when both E and A are present (i.e., except for alternating automata), and that E and A represent unlimited savings in succinctness in all cases.

We consider infinite recursive (i.e., computable) relational data bases. Since the set of computable queries on such data bases is not closed under even simple relational operations, one must either make do with a very modest class of queries or considerably restrict the class of allowed data bases. We define two query languages, one for each of these possibilities, and prove their completeness. The first is the language of quantifier-free first-order logic, which is shown to be complete for the non-restricted case. The second is an appropriately modified version of Chandra and Harel's language QL, which is proved complete for the case of ``highly symmetric" data bases, i.e., ones whose set of automorphisms is of finite index for each tuple-width. We also address the related notion of BP-completeness.