Weak Second‐Order Arithmetic and Finite Automata

DOI10.1002/MALQ.19600060105zbMath0103.24705OpenAlexW4205178514MaRDI QIDQ3287248

Publication date: 1960

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.19600060105

zbMATH Keywords

logics, foundations, philosophy

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Related Items (only showing first 100 items - show all)

Monadic second-order definable graph transductions: a survey ⋮ Modulo-counting quantifiers over finite trees ⋮ Trees, grids, and MSO decidability: from graphs to matroids ⋮ Timed hyperproperties ⋮ On an approach to functional specification of automata systems. II ⋮ A logical approach of Petri net languages ⋮ A logical approach to locality in pictures languages ⋮ Existential MSO over two successors is strictly weaker than over linear orders ⋮ Weighted automata and weighted logics with discounting ⋮ Efficient algorithms for membership in Boolean hierarchies of regular languages ⋮ Definable transductions and weighted logics for texts ⋮ Weighted automata and weighted logics on infinite words ⋮ Factorization forests for infinite words and applications to countable scattered linear orderings ⋮ On the dependence of numeration systems associated to the powers of a Pisot number ⋮ ALOGTIME and a conjecture of S. A. Cook ⋮ LARS: a logic-based framework for analytic reasoning over streams ⋮ Monadic second-order definable text languages ⋮ Automata on linear orderings ⋮ Semigroups and languages of dot-depth two ⋮ Skew and infinitary formal power series ⋮ Weighted tree automata and weighted logics ⋮ Logic programming approach to automata-based decision procedures ⋮ Regular language representations in the constructive type theory of Coq ⋮ Expressiveness and complexity of graph logic ⋮ Algorithmic uses of the Feferman-Vaught theorem ⋮ Undecidability of the first-order arithmetic \(A[P(x),2x,x+1\)] ⋮ On Pascal triangles modulo a prime power ⋮ Theories of generalized Pascal triangles ⋮ Ehrenfeucht games and ordinal addition ⋮ Inverse monoids of dot-depth two ⋮ FO(ID) as an extension of DL with rules ⋮ Determinization of ordinal automata ⋮ Logical description of context-free graph languages ⋮ Bertrand numeration systems and recognizability ⋮ The sum of digits of squares ⋮ Ambiguity in omega context free languages ⋮ Borel hierarchy and omega context free languages. ⋮ The definable criterion for definability in Presburger arithmetic and its applications. ⋮ A descriptive complexity approach to the linear hierarchy. ⋮ Schützenberger and Eilenberg theorems for words on linear orderings ⋮ XML with data values: Typechecking revisited. ⋮ Büchi context-free languages ⋮ Probabilistic contracts: a compositional reasoning methodology for the design of systems with stochastic and/or non-deterministic aspects ⋮ Complexity of algorithms and computations ⋮ Automata and logics over finitely varying functions ⋮ Model-theoretic complexity of automatic structures ⋮ Aural pattern recognition experiments and the subregular hierarchy ⋮ Generalizing input-driven languages: theoretical and practical benefits ⋮ Testable and untestable classes of first-order formulae ⋮ A finite state intersection approach to propositional satisfiability ⋮ Impugning randomness, convincingly ⋮ Static analysis of XML security views and query rewriting ⋮ Inferring answers to queries ⋮ Classifying regular events in symbolic logic ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Realization problems for nonuniform cellular automata ⋮ The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability ⋮ A regular characterization of graph languages definable in monadic second-order logic ⋮ The expressivity of autosegmental grammars ⋮ Explicit linear kernels for packing problems ⋮ Logically defined subsets of \(\mathbb{N}{}^ k\) ⋮ Exact complexity bounds for ordinal addition ⋮ Monadic partition logics and finite automata ⋮ Copyless cost-register automata: structure, expressiveness, and closure properties ⋮ Topological complexity of locally finite \(\omega\)-languages ⋮ A note on the number of monadic quantifiers in monadic \(\Sigma ^{1}_{1}\) ⋮ Positive existential definability of multiplication from addition and the range of a polynomial ⋮ Multi-weighted automata and MSO logic ⋮ On automatic subsets of the Gaussian integers ⋮ The descriptive complexity of decision problems through logics with relational fixed-point and capturing results ⋮ Regular languages in \(NC\) ⋮ Muller message-passing automata and logics ⋮ Fine hierarchies and m-reducibilities in theoretical computer science ⋮ Formulas, regular languages and Boolean circuits ⋮ Completeness for the modal \(\mu\)-calculus: separating the combinatorics from the dynamics ⋮ Deciding game invariance ⋮ On the path-width of integer linear programming ⋮ Weighted automata and logics for infinite nested words ⋮ Ostrowski numeration systems, addition, and finite automata ⋮ The theory of \(\langle \mathbb{N} , +, V_ k, V_ l\rangle\) is undecidable ⋮ A Büchi-like theorem for weighted tree automata over multioperator monoids ⋮ Characterizations of complete residuated lattice-valued finite tree automata ⋮ Series-parallel languages on scattered and countable posets ⋮ Theories of automata on \(\omega\)-tapes: a simplified approach ⋮ Ehrenfeucht-Fraïssé goes automatic for real addition ⋮ First-order logics: some characterizations and closure properties ⋮ Logic and rational languages of words indexed by linear orderings ⋮ The algebraic theory of Parikh automata ⋮ An axiom system for the weak monadic second order theory of two successors ⋮ Presburgerness of predicates regular in two number systems ⋮ Mathematical logic and quantum finite state automata ⋮ Don't care words with an application to the automata-based approach for real addition ⋮ Weighted automata and multi-valued logics over arbitrary bounded lattices ⋮ On relation between linear temporal logic and quantum finite automata ⋮ A comparison of tree transductions defined by monadic second order logic and by attribute grammars ⋮ The monadic second-order logic of graphs. IV: Definability properties of equational graphs ⋮ Logic over words on denumerable ordinals ⋮ Query automata over finite trees ⋮ Decidability of extended theories of addition of the natural numbers and the integers ⋮ Relativizations for the logic-automata connection

Cites Work

This page was built for publication: Weak Second‐Order Arithmetic and Finite Automata