Results 1 to 10 of about 47,932 (337)
A new proof for the decidability of D0L ultimate periodicity [PDF]
Electronic Proceedings in Theoretical Computer Science, 2011 We give a new proof for the decidability of the D0L ultimate periodicity problem based on the decidability of p-periodicity of morphic words adapted to the approach of Harju and Linna.
Vesa Halava, Tero Harju, Tomi Kärki
doaj +4 more sources
Decision Problems for Deterministic Pushdown Automata on Infinite Words [PDF]
Electronic Proceedings in Theoretical Computer Science, 2014 The article surveys some decidability results for DPDAs on infinite words (omega-DPDA). We summarize some recent results on the decidability of the regularity and the equivalence problem for the class of weak omega-DPDAs.
Christof Löding
doaj +4 more sources
Decidability Results for the Boundedness Problem [PDF]
Logical Methods in Computer Science, 2014 We prove decidability of the boundedness problem for monadic least fixed-point recursion based on positive monadic second-order (MSO) formulae over trees.
Achim Blumensath +2 more
doaj +3 more sources
Trees over Infinite Structures and Path Logics with Synchronization [PDF]
Electronic Proceedings in Theoretical Computer Science, 2011 We provide decidability and undecidability results on the model-checking problem for infinite tree structures. These tree structures are built from sequences of elements of infinite relational structures.
Alex Spelten +2 more
doaj +4 more sources
A Syntactic Proof of the Decidability of First-Order Monadic Logic
Bulletin of the Section of LogicDecidability of monadic first-order classical logic was established by Löwenheim in 1915. The proof made use of a semantic argument and a purely syntactic proof has never been provided.
Eugenio Orlandelli
exaly +3 more sources
Chimerical Dataset Creation Protocol Based on Doddington Zoo: A Biometric Application with Face, Eye, and ECG [PDF]
Sensors, 2019 Multimodal systems are a workaround to enhance the robustness and effectiveness of biometric systems. A proper multimodal dataset is of the utmost importance to build such systems.
Pedro Lopes Silva +4 more
doaj +2 more sources
General Decidability Results for Asynchronous Shared-Memory Programs: Higher-Order and Beyond [PDF]
Logical Methods in Computer Science, 2022 The model of asynchronous programming arises in many contexts, from low-level systems software to high-level web programming. We take a language-theoretic perspective and show general decidability and undecidability results for asynchronous programs that
Rupak Majumdar +2 more
doaj +1 more source
Resynchronized Uniformization and Definability Problems for Rational Relations [PDF]
Discrete Mathematics & Theoretical Computer Science, 2023 Regular synchronization languages can be used to define rational relations of finite words, and to characterize subclasses of rational relations, like automatic or recognizable relations.
Christof Löding, Sarah Winter
doaj +1 more source
Philosophies, 2023 The “somewhat vague, intuitive” notion from computability theory of an effective procedure (method) or algorithm can be fairly precisely defined, even if it does not have a purely mathematical definition—and even if (as many have asserted) for that ...
Nathan Salmon
doaj +1 more source
Decidability Preservation and Complexity Bounds for Combined Logics
Mathematics, 2022 Transfer theorems for combined logics provide essential tools and insight for reasoning about complex logical systems. In this paper, we present the first sufficient criterion (contextual extensibility) for decidability to be preserved through ...
Carlos Caleiro, Sérgio Marcelino
doaj +1 more source