Monadic decomposability of regular relations

DOI10.4230/LIPICS.ICALP.2019.103MaRDI QIDQ5091265zbMATH OpenFDO

Authors Pablo Barceló, Chih-Duo Hong, Xuan-Bach Le, Reino Niskanen, Anthony Widjaja Lin

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1903.00728

zbMATH Keywords

automataautomatic structuresRamsey theorysynchronized rational relationstransducersvariable independence

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Recommendations

• Decision problems among the main subfamilies of rational relations
• scientific article; zbMATH DE number 7058469
• Deciding Whether or Not a Synchronous Relation is Regular Prefix
• Decision problems for subclasses of rational relations over finite and infinite words
• Monadic decomposition

Cites work

• A regularity test for pushdown machines
• Computability and Logic
• Decision problems among the main subfamilies of rational relations
• Decision problems for subclasses of rational relations over finite and infinite words
• Definable relations and first-order query languages over strings
• Elements of automata theory. Translated from the French by Reuben Thomas
• scientific article; zbMATH DE number 1670829 (Why is no real title available?)
• scientific article; zbMATH DE number 3841819 (Why is no real title available?)
• scientific article; zbMATH DE number 5595162 (Why is no real title available?)
• scientific article; zbMATH DE number 5605092 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 7058469 (Why is no real title available?)
• scientific article; zbMATH DE number 965572 (Why is no real title available?)
• Logical queries over views, decidability and expressiveness
• Monadic decomposition
• Multitape one-way nonwriting automata
• On Relations Defined by Generalized Finite Automata
• Recurrent Reachability Analysis in Regular Model Checking
• Regularity and Related Problems for Deterministic Pushdown Automata
• String solving with word equations and transducers: towards a logic for analysing mutation XSS
• Synchronized rational relations of finite and infinite words
• Transductions des langages de Chomsky
• Transforming structures by set interpretations

Cited in

(5)

• Monadic decomposition in integer linear arithmetic
• Monadic representability of certain binary relations
• Ramsey quantifiers over automatic structures: complexity and applications to verification
• Synthesising full-information protocols
• Learning union of integer hypercubes with queries (with applications to monadic decomposition)

This page was built for publication: Monadic decomposability of regular relations

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