Weak Second‐Order Arithmetic and Finite Automata

From MaRDI portal

Publication:3287248

Jump to:navigation, search

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

J. Richard Buchi

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

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, On omega context free languages which are Borel sets of infinite rank., Describing parameterized complexity classes, On iterating linear transformations over recognizable sets of integers, Closure properties of locally finite \(\omega\)-languages, Arithmetical definability and computational complexity, The complexity of first-order and monadic second-order logic revisited, Regular sets of infinite message sequence charts, Weighted automata and weighted logics, Approach to functional specification of automaton systems. I, Weighted Register Automata and Weighted Logic on Data Words, LOGICAL CHARACTERIZATION OF RECOGNIZABLE SETS OF POLYNOMIALS OVER A FINITE FIELD, Complementation of rational sets on scattered linear orderings of finite rank, An algebra and a logic for \(NC^ 1\), Arity and alternation: a proper hierarchy in higher order logics, On uniformity within \(NC^ 1\), Decision algorithms for Fibonacci-automatic Words, I: Basic results, The monadic second-order logic of graphs. I: Recognizable sets of finite graphs, Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition, Computability by monadic second-order logic, Inclusion relations between some congruences related to the dot-depth hierarchy, Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees, Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems, Arity and alternation in second-order logic, Rational elements of summation semirings, The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy, McCarthy-Kleene fuzzy automata and MSO logics, Logics for Weighted Timed Pushdown Automata, Automata and Logics for Concurrent Systems: Five Models in Five Pages, A computation model with automatic functions and relations as primitive operations, Alternation Hierarchies of First Order Logic with Regular Predicates, Weighted automata and weighted MSO logics for average and long-time behaviors, Logics for unordered trees with data constraints, Effective categoricity of automatic equivalence and nested equivalence structures, Weighted logics for unranked tree automata, Uncountable automatic classes and learning, Deciding FO-definability of regular languages, Tree languages and branched groups, Communicating finite-state machines, first-order logic, and star-free propositional dynamic logic, Operator precedence temporal logic and model checking, On the expressiveness of Büchi arithmetic, Shared-Memory Systems and Charts, First-order rewritability of ontology-mediated queries in linear temporal logic, Expressing cardinality quantifiers in monadic second-order logic over chains, Additive number theory via automata theory, Cobham-Semenov theorem and \(\mathbb N^d\)-subshifts, Event clock message passing automata: a logical characterization and an emptiness checking algorithm, MONA IMPLEMENTATION SECRETS, Automatic sequences based on Parry or Bertrand numeration systems, Algebraic recognizability of regular tree languages, Weak Muller acceptance conditions for tree automata, It is decidable whether the image of an \(\mathbb N\)-rational sequence has a base, Attribute grammars for unranked trees as a query language for structured documents, Robustness of Pisot-regular sequences, Subsequence versus substring constraints in sequence pattern languages, Message-passing automata are expressively equivalent to EMSO logic, Pro-aperiodic monoids via saturated models, Weighted register automata and weighted logic on data words, The monadic quantifier alternation hierarchy over grids and graphs, Decidable \({\exists}^*{\forall}^*\) first-order fragments of linear rational arithmetic with uninterpreted predicates, Streamable regular transductions, A unifying survey on weighted logics and weighted automata. Core weighted logic: minimal and versatile specification of quantitative properties, Quantifier Alternation for Infinite Words, A Class of Automata for the Verification of Infinite, Resource-Allocating Behaviours, Defining Multiplication in Some Additive Expansions of Polynomial Rings, Kleene and Büchi theorems for weighted forest languages over M-monoids, Weighted Automata and Logics on Infinite Graphs, On Finite and Polynomial Ambiguity of Weighted Tree Automata, On the width of regular classes of finite structures, Bounds in the propagation of selection into logic programs, Causality in Bounded Petri Nets is MSO Definable, Decidability results for metric and layered temporal logics, Logic, semigroups and automata on words, Tree acceptors and some of their applications, Weighted operator precedence languages, Logic for \(\omega\)-pushdown automata, Weighted Tree Automata over Valuation Monoids and Their Characterization by Weighted Logics, Operations on Weakly Recognizing Morphisms, A Logical Characterization of Small 2NFAs, A Decision Procedure for Regular Expression Equivalence in Type Theory, The monadic second-order logic of graphs. VIII: Orientations, On decidability of list structures, On an approach to functional specification of automata systems. III, On distinguishing sets of structures by first-order sentences of minimal quantifier rank, Product interval automata, A theory of regular MSC languages, Models for quantitative distributed systems and multi-valued logics, Automata techniques for query inference machines, A reducibility for the dot-depth hierarchy, Uniform and nonuniform recognizability., Star-free sets of words on ordinals, Languages defined with modular counting quantifiers, The many faces of a translation, Decidability and undecidability of theories with a predicate for the primes, Decidability of a Hybrid Duration Calculus, Array theory of bounded elements and its applications, Algebraic model checking for discrete linear dynamical systems, A conjecture on the concatenation product, A link between multioperator and tree valuation automata and logics, An operational and denotational approach to non-context-freeness, wMSO theories as grammar formalisms, On the base-dependence of sets of numbers recognizable by finite automata, Generalized finite automata theory with an application to a decision problem of second-order logic, Decision methods in the theory of ordinals, First-order Logic with Connectivity Operators, On the existential arithmetics with addition and bitwise minimum, On interpretations of Presburger arithmetic in Büchi arithmetics, Addition machines, automatic functions and open problems of Floyd and Knuth, Magic Numbers in Periodic Sequences, Automaticity and Parikh-Collinear Morphisms, Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages, Knapsack and the power word problem in solvable Baumslag–Solitar groups, On algebraic array theories, Universal first-order quantification over automata, A General Approach to Proving Properties of Fibonacci Representations via Automata Theory, Uniform tag sequences, Unnamed Item, A Logical Characterisation of Event Clock Automata, On Expressive Power of Regular Expressions over Infinite Orders, Locally finite languages, A list of arithmetical structures complete with respect to the first-order definability, Topological properties of omega context-free languages, Wadge hierarchy of omega context-free languages, Incremental reasoning on monadic second-order logics with logic programming, Logic and rational languages of scattered and countable series-parallel posets, Unnamed Item, Decidability and undecidability of extensions of second (first) order theory of (generalized) successor, Generalized finite automata theory with an application to a decision problem of second-order logic, A Model-Theoretic Description of Tree Adjoining Grammars1 1The research presented in this paper was supported by the Deutsche Forschungsgemeinschaft within the Sonderforschungsbereich 441, TP A2. The authors wish to thank Jens Michaelis and Stephan Kepser for helpful comments., On multiplicatively dependent linear numeration systems, and periodic points, Weight Assignment Logic, First-order properties of trees, star-free expressions, and aperiodicity, ON WEIGHTED BÜCHI AUTOMATA WITH ORDER-COMPLETE WEIGHTS, Generalized rational relations and their logical definability, Unnamed Item, A Logical Characterization of Small 2NFAs, Weighted Automata and Weighted Logics, A Logical Characterization of Timed Pushdown Languages, Rational, recognizable, and aperiodic partially lossy queue languages, Unnamed Item, Star-free picture expressions are strictly weaker than first-order logic, Recognizability equals definability for partial k-paths, Presburger Arithmetic, Rational Generating Functions, and Quasi-Polynomials, Regular canonical systems, Extensions of an idea of McNaughton, Recognizable sets of numbers in nonstandard bases, Joining k- and l-recognizable sets of natural numbers, MSO definable text languages, Unnamed Item, Rudin–Shapiro sequences along squares, Logical definability of some rational trace languages, Tailoring recursion for complexity, Model Theoretic Complexity of Automatic Structures (Extended Abstract), Automata Presenting Structures: A Survey of the Finite String Case, Weighted Automata and Weighted Logics with Discounting, Classifying the computational complexity of problems, Unnamed Item, The theory of integer multiplication with order restricted to primes is decidable, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS, Topology for Computations of Concurrent Automata, Impartial Anticipation in Runtime-Verification, Upper Bounds on the Automata Size for Integer and Mixed Real and Integer Linear Arithmetic (Extended Abstract), Weak Second‐Order Arithmetic and Finite Automata, First-order and counting theories ofω-automatic structures, y= 2xVS.y= 3x, Cobham's Theorem seen through Büchi's Theorem, The product of rational languages, Resynchronizing Classes of Word Relations, Undecidable extensions of Büchi arithmetic and Cobham-Semënov Theorem, ON RECOGNIZABLE LANGUAGES OF INFINITE PICTURES, Effective optimization with weighted automata on decomposable trees, A Practical Approach to Courcelle's Theorem, Networks of Processes with Parameterized State Space, The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey, Definability of Combinatorial Functions and Their Linear Recurrence Relations, UNAMBIGUOUS SHARED-MEMORY SYSTEMS, Unnamed Item, Complementation of Branching Automata for Scattered and Countable N-Free Posets, Unnamed Item, From Philosophical to Industrial Logics, Unnamed Item, Unnamed Item, Unnamed Item, Variable and Clause Ordering in an FSA Approach to Propositional Satisfiability, Compositional Failure Detection in Structured Transition Systems, An extension of the Cobham-Semënov Theorem, From Logic to Theoretical Computer Science – An Update, Selection and Uniformization Problems in the Monadic Theory of Ordinals: A Survey, Church’s Problem and a Tour through Automata Theory, From Monadic Logic to PSL, Circuit complexity and the expressive power of generalized first-order formulas, The 2007 Annual Conference of the Australasian Association for Logic, Facets of Synthesis: Revisiting Church’s Problem, Turing Computations On Ordinals, Theories of arithmetics in finite models, On Verifying Fault Tolerance of Distributed Protocols, Automata and Logics for Timed Message Sequence Charts, Unnamed Item, Unnamed Item, COMPLEMENTATION OF RATIONAL SETS ON COUNTABLE SCATTERED LINEAR ORDERINGS, Unnamed Item, Where First-Order and Monadic Second-Order Logic Coincide, Pomset Languages of Finite Step Transition Systems, The complexity of weakly recognizing morphisms, Weighted versus Probabilistic Logics, Closure properties of synchronized relations, PITL2MONA: Implementing a Decision Procedure for Propositional Interval Temporal Logic, Unnamed Item, CARDINAL ARITHMETIC IN THE STYLE OF BARON VON MÜNCHHAUSEN, A KLEENE THEOREM FOR LANGUAGES OF WORDS INDEXED BY LINEAR ORDERINGS, Relational Properties Expressible with One Universal Quantifier Are Testable, Uncountable Automatic Classes and Learning, Monitor Logics for Quantitative Monitor Automata, Weighted Operator Precedence Languages, Unnamed Item, On sets of relations definable by addition, RECOGNIZABLE AND LOGICALLY DEFINABLE LANGUAGES OF INFINITE COMPUTATIONS IN CONCURRENT AUTOMATA, On the Class of Predicates Decidable by Two-Way Multitape Finite Automata, Complexity classes and theories of finite models, Decision problems for multiple successor arithmetics, State-strategies for games in F_σδ ∩ G_δσ

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:3287248&oldid=16499595"