Decision problems among the main subfamilies of rational relations

DOI10.1051/ita:2006005zbMath1112.03008OpenAlexW2126533781MaRDI QIDQ3431438

Olivier Carton, Serge Grigorieff, Christian Choffrut

Publication date: 10 April 2007

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2006__40_2_255_0

zbMATH Keywords

decision problemsmultitape automataPresburger arithmetics

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)

Related Items

Learning union of integer hypercubes with queries (with applications to monadic decomposition) ⋮ Deciding whether a relation defined in Presburger logic can be defined in weaker logics ⋮ Synchronizing relations on words ⋮ Preface ⋮ Resynchronizing Classes of Word Relations ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An Automata Theoretic Approach to Rational Tree Relations ⋮ Monadic decomposition in integer linear arithmetic ⋮ Uniform strategies, rational relations and jumping automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Subclasses of Presburger arithmetic and the polynomial-time hierarchy
• Semigroups, Presburger formulas, and languages
• Multitape one-way nonwriting automata
• Rational sets in commutative monoids
• Sets recognized by n-tape automata
• Regularity and Related Problems for Deterministic Pushdown Automata
• The Unsolvability of the Equivalence Problem for $\varepsilon $-Free NGSM’s with Unary Input (Output) Alphabet and Applications
• On Relations Defined by Generalized Finite Automata
• A regularity test for pushdown machines