Decision Problems of Finite Automata Design and Related Arithmetics
From MaRDI portal
Publication:3848195
DOI10.2307/1993511zbMath0111.01102OpenAlexW4243535863MaRDI QIDQ3848195
Publication date: 1962
Full work available at URL: https://doi.org/10.2307/1993511
Related Items (only showing first 100 items - show all)
Monadic second-order definable graph transductions: a survey ⋮ Modulo-counting quantifiers over finite trees ⋮ Influence decision models: from cooperative game theory to social network analysis ⋮ Arithmetical definability and computational complexity ⋮ 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 ⋮ Weighted automata and weighted logics with discounting ⋮ Definable transductions and weighted logics for texts ⋮ Weighted automata and weighted logics on infinite words ⋮ An algebra and a logic for \(NC^ 1\) ⋮ LARS: a logic-based framework for analytic reasoning over streams ⋮ Trading transforms of non-weighted simple games and integer weights of weighted simple games ⋮ Weighted tree automata and weighted logics ⋮ A Logical Characterization of Timed Pushdown Languages ⋮ Logic programming approach to automata-based decision procedures ⋮ Computability by monadic second-order logic ⋮ Regular language representations in the constructive type theory of Coq ⋮ Algorithmic uses of the Feferman-Vaught theorem ⋮ Inclusion relations between some congruences related to the dot-depth hierarchy ⋮ Rational elements of summation semirings ⋮ Logical description of context-free graph languages ⋮ The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy ⋮ Communicating Finite-State Machines and Two-Variable Logic ⋮ McCarthy-Kleene fuzzy automata and MSO logics ⋮ Logics for Weighted Timed Pushdown Automata ⋮ Weighted automata and weighted MSO logics for average and long-time behaviors ⋮ A generalization of the theory of incompletely specified machines ⋮ Weighted Automata and Weighted Logics with Discounting ⋮ A descriptive complexity approach to the linear hierarchy. ⋮ Weighted logics for unranked tree automata ⋮ In memoriam Calvin C. Elgot ⋮ Deciding FO-definability of regular languages ⋮ Quantitative vs. weighted automata ⋮ Aural pattern recognition experiments and the subregular hierarchy ⋮ Generalizing input-driven languages: theoretical and practical benefits ⋮ A finite state intersection approach to propositional satisfiability ⋮ Communicating finite-state machines, first-order logic, and star-free propositional dynamic logic ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Isomorphisms of scattered automatic linear orders ⋮ The complexity of computing the behaviour of lattice automata on infinite trees ⋮ Weak Second‐Order Arithmetic and Finite Automata ⋮ Classifying regular events in symbolic logic ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ A regular characterization of graph languages definable in monadic second-order logic ⋮ A note on the number of monadic quantifiers in monadic \(\Sigma ^{1}_{1}\) ⋮ First-order rewritability of ontology-mediated queries in linear temporal logic ⋮ Multi-weighted automata and MSO logic ⋮ Muller message-passing automata and logics ⋮ On Turing degrees of Walrasian models and a general impossibility result in the theory of decision-making ⋮ Weighted automata and logics for infinite nested words ⋮ Event clock message passing automata: a logical characterization and an emptiness checking algorithm ⋮ A Büchi-like theorem for weighted tree automata over multioperator monoids ⋮ Algebraic recognizability of regular tree languages ⋮ Theories of automata on \(\omega\)-tapes: a simplified approach ⋮ The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey ⋮ From Philosophical to Industrial Logics ⋮ Message-passing automata are expressively equivalent to EMSO logic ⋮ The monadic quantifier alternation hierarchy over grids and graphs ⋮ Streamable regular transductions ⋮ A unifying survey on weighted logics and weighted automata. Core weighted logic: minimal and versatile specification of quantitative properties ⋮ Expressibility in a restricted second-order arithmetic ⋮ Quantifier Alternation for Infinite Words ⋮ A Class of Automata for the Verification of Infinite, Resource-Allocating Behaviours ⋮ Maximin sequential chains ⋮ Weighted Automata and Logics on Infinite Graphs ⋮ On Finite and Polynomial Ambiguity of Weighted Tree Automata ⋮ Mathematical logic and quantum finite state automata ⋮ On the width of regular classes of finite structures ⋮ Bounds in the propagation of selection into logic programs ⋮ Weighted versus Probabilistic Logics ⋮ Weighted Timed MSO Logics ⋮ Equidivisible semigroups ⋮ Logic, semigroups and automata on words ⋮ Generalized sequential machine maps ⋮ 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 ⋮ Where Automatic Structures Benefit from Weighted Automata ⋮ Weighted automata and multi-valued logics over arbitrary bounded lattices ⋮ AFL with the semilinear property ⋮ Weighted automata ⋮ Automata on finite trees ⋮ On relation between linear temporal logic and quantum finite automata ⋮ The isomorphism problem on classes of automatic structures with transitive relations ⋮ Some Remarks on Abstract Machines ⋮ A comparison of tree transductions defined by monadic second order logic and by attribute grammars ⋮ Calvin C. Elgot (1922-1980) ⋮ A reducibility for the dot-depth hierarchy ⋮ Classes of Predictably Computable Functions ⋮ Projection lemmas for \(\omega\)-languages ⋮ Uniform and nonuniform recognizability. ⋮ Decidability of a Hybrid Duration Calculus ⋮ Relativizations for the logic-automata connection ⋮ A link between multioperator and tree valuation automata and logics ⋮ Shelah-Stupp's and Muchnik's iterations revisited ⋮ An operational and denotational approach to non-context-freeness ⋮ wMSO theories as grammar formalisms
Cites Work
This page was built for publication: Decision Problems of Finite Automata Design and Related Arithmetics
