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
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, 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., A universal two-way automaton, First-order properties of trees, star-free expressions, and aperiodicity, Maximin sequential-like machines and chains, Weighted Automata and Weighted Logics, Decision methods in the theory of ordinals, Unnamed Item, Regular prefix relations, Logical definability of some rational trace languages, On the existential arithmetics with addition and bitwise minimum, Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages, Uniform tag sequences, Unnamed Item, The product of rational languages, Unnamed Item, Pebble Weighted Automata and Weighted Logics, A Practical Approach to Courcelle's Theorem, Verifying a Network Invariant for All Configurations of the Futurebus+ Cache Coherence Protocol, Networks of Processes with Parameterized State Space, On Expressive Power of Regular Expressions over Infinite Orders, A list of arithmetical structures complete with respect to the first-order definability, Unnamed Item, Complementation of Branching Automata for Scattered and Countable N-Free Posets, Unnamed Item, Unnamed Item, Compositional Failure Detection in Structured Transition Systems, 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, Incremental reasoning on monadic second-order logics with logic programming, On Verifying Fault Tolerance of Distributed Protocols, Unnamed Item, Where First-Order and Monadic Second-Order Logic Coincide, Logic and rational languages of scattered and countable series-parallel posets, Automatic Structures of Bounded Degree Revisited, CARDINAL ARITHMETIC IN THE STYLE OF BARON VON MÜNCHHAUSEN, Monitor Logics for Quantitative Monitor Automata, Weighted Operator Precedence Languages, On the Class of Predicates Decidable by Two-Way Multitape Finite Automata, Complexity classes and theories of finite models
Cites Work
