Sequentiality, monadic second-order logic and tree automata.

DOI10.1006/inco.1999.2838zbMath1051.68086OpenAlexW2011805144MaRDI QIDQ1854333

Hubert Comon

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1999.2838

zbMATH Keywords

term rewriting system

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Grammars and rewriting systems (68Q42) Second- and higher-order model theory (03C85)

Related Items (10)

Unnamed Item ⋮ Linear algebra for tensor problems ⋮ A polynomial algorithm for uniqueness of normal forms of linear shallow term rewrite systems ⋮ First-order theory of rewriting for linear variable-separated rewrite systems: automation, formalization, certification ⋮ Decidability for left-linear growing term rewriting systems. ⋮ Certifying proofs in the first-order theory of rewriting ⋮ Formalized Proofs of the Infinity and Normal Form Predicates in the First-Order Theory of Rewriting ⋮ Decidable call-by-need computations in term rewriting ⋮ Strong and NV-sequentiality of constructor systems ⋮ Context-sensitive rewriting strategies

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Programming in equational logic: Beyond strong sequentiality
• Computing in systems described by equations
• Sequentiality in orthogonal term rewriting systems
• Equational formulae with membership constraints
• Sequential evaluation strategies for parallel-or and related reduction systems
• Deciding Equivalence of Finite Tree Automata
• NV-Sequentiality: A Decidable Condition for Call-by-Need Computations in Term-Rewriting Systems
• Encompassment properties and automata with constraints
• Equality and disequality constraints on direct subterms in tree automata
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Decidability of Second-Order Theories and Automata on Infinite Trees

This page was built for publication: Sequentiality, monadic second-order logic and tree automata.