Generalized finite automata theory with an application to a decision problem of second-order logic

DOI10.1007/BF01691346zbMath0196.01901MaRDI QIDQ5592253

Jesse B. Wright, James W. Thatcher

Publication date: 1968

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Mathematics Subject Classification ID

Algebraic theory of languages and automata (68Q70)

Related Items

Similarity-based minimization of fuzzy tree automata, Algebraic properties of complete residuated lattice valued tree automata, Mappings and grammars on trees, Deciding Boolean algebra with Presburger arithmetic, XML schema, tree logic and sheaves automata, Some structural properties of generalized automata and algebras, Regular prefix relations, Weighted logics for unranked tree automata, Some results in tree automata, Stochastic grammars and languages, A medvedev characterization of sets recognized by generalized finite automata, Bottom-up and top-down tree transformations— a comparison, A Büchi-like theorem for weighted tree automata over multioperator monoids, Pushdown tree automata, Querying linguistic treebanks with monadic second-order logic in linear time, Cascades of tree-automata and computations in universal algebras, A Kleene theorem for weighted tree automata over distributive multioperator monoids, Weighted tree automata with constraints, Le théorème de transversale rationnelle dans les langages d'arbres, Automata terms in a lazy \(\mathrm{WS}k\mathrm{S}\) decision procedure, Inessential features, ineliminable features, and modal logics for model theoretic syntax, Automata terms in a lazy \(\mathrm{WS}k\mathrm{S}\) decision procedure, Unnamed Item, Nested Sibling Tree Automata, Transductions of dags and trees, Hierarchies of weak automata and weak monadic formulas, Determinacy of sinking automata on infinite trees and inequalities between various Rabin's pair indices, Characterization of tree automata based on quantum logic, On two families of forests

Cites Work

• Unnamed Item
• Unnamed Item
• Realization of Events by Logical Nets
• The first order properties of products of algebraic systems
• Weak Second‐Order Arithmetic and Finite Automata
• Classes of Predictably Computable Functions
• Restricted Set-Theoretical Definitions in Arithmetic
• Beitrag zur Aerodynamik eines schwingenden Gitters II (Unterschallströmung)