Monadic decomposition

DOI10.1145/3040488MaRDI QIDQ4640286zbMATH OpenOpenAlexWikidataFDO

Authors Margus Veanes, Nikolaj Bjørner, Lev Nachmanson, Sergey Bereg

Publication date 17 May 2018

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3040488

zbMATH Keywords

monadic logicsatisfiability modulo theoriessymbolic automatavariable independence

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Automata and formal grammars in connection with logical questions (03D05)

Recommendations

• Synthesizing Monadic Predicates
• On decidability of monadic logic of order over the naturals extended by monadic predicates
• A decidable fragment of predicate calculus
• Decidability of the monadic shallow linear first-order fragment with straight dismatching constraints

Cited in

(13)

• Monoidal multiplexing
• Monadic decomposition in integer linear arithmetic
• A layered algorithm for quantifier elimination from linear modular constraints
• Monoids and decay
• Monadic decomposability of regular relations
• Monotonicity inference for higher-order formulas
• Quantifier elimination for counting extensions of Presburger arithmetic
• Ramsey quantifiers over automatic structures: complexity and applications to verification
• An efficient quantifier elimination procedure for Presburger arithmetic
• The complexity of separability for semilinear sets and Parikh automata
• Negated string containment is decidable
• Extended symbolic finite automata and transducers
• Learning union of integer hypercubes with queries (with applications to monadic decomposition)

This page was built for publication: Monadic decomposition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4640286)