Finite automata, real time processes and counting problems in bounded arithmetics

Journal of Symbolic Logic 53 (1):243-258 (1988)
  Copy   BIBTEX

Abstract

In this paper we present a negative solution of counting problems for some classes slightly different from bounded arithmetic (▵ 0 sets). To get the results we study properties of chains of finite automata.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,261

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Automata presenting structures: A survey of the finite string case.Sasha Rubin - 2008 - Bulletin of Symbolic Logic 14 (2):169-209.
Computational Semantics for Monadic Quantifiers.Marcin Mostowski - 1998 - Journal of Applied Non--Classical Logics 8 (1-2):107--121.
Semi-Bounded Relations in Ordered Modules.Oleg Belegradek - 2004 - Journal of Symbolic Logic 69 (2):499 - 517.
Complexity of the two-variable fragment with counting quantifiers.Ian Pratt-Hartmann - 2005 - Journal of Logic, Language and Information 14 (3):369-395.
Theories of arithmetics in finite models.Michał Krynicki & Konrad Zdanowski - 2005 - Journal of Symbolic Logic 70 (1):1-28.
Weak Cardinality Theorems.Till Tantau - 2005 - Journal of Symbolic Logic 70 (3):861 - 878.

Analytics

Added to PP
2009-01-28

Downloads
31 (#518,746)

6 months
8 (#370,225)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references