Breaking intractability of spanning caterpillar tree problem: A logical approach [PDF]
AUT Journal of Mathematics and Computing, 2022 In this paper we pursue a logical approach to prove that the optimisation problem of finding a spanning caterpillar tree in a graph has polynomial algorithm for bounded tree width graphs.
Masoud Khosravani
doaj +1 more source
A Functional (Monadic) Second-Order Theory of Infinite Trees [PDF]
Logical Methods in Computer Science, 2020 This paper presents a complete axiomatization of Monadic Second-Order Logic (MSO) over infinite trees. MSO on infinite trees is a rich system, and its decidability ("Rabin's Tree Theorem") is one of the most powerful known results concerning the ...
Anupam Das, Colin Riba
doaj +1 more source
An expressive completeness theorem for coalgebraic modal mu-calculi [PDF]
Logical Methods in Computer Science, 2017 Generalizing standard monadic second-order logic for Kripke models, we introduce monadic second-order logic interpreted over coalgebras for an arbitrary set functor. We then consider invariance under behavioral equivalence of MSO-formulas.
Sebastian Enqvist +2 more
doaj +1 more source
Local Normal Forms for First-Order Logic with Applications to Games and Automata [PDF]
Discrete Mathematics & Theoretical Computer Science, 1999 Building on work of Gaifman [Gai82] it is shown that every first-order formula is logically equivalent to a formula of the form ∃ x 1,...,x l, ∀ y, φ where φ is r-local around y, i.e.
Thomas Schwentick, Klaus Barthelmann
doaj +2 more sources
Regular Cost Functions, Part I: Logic and Algebra over Words [PDF]
Logical Methods in Computer Science, 2013 The theory of regular cost functions is a quantitative extension to the classical notion of regularity. A cost function associates to each input a non-negative integer value (or infinity), as opposed to languages which only associate to each input the ...
Thomas Colcombet
doaj +1 more source
On the Expressive Power of 2-Stack Visibly Pushdown Automata [PDF]
Logical Methods in Computer Science, 2008 Visibly pushdown automata are input-driven pushdown automata that recognize some non-regular context-free languages while preserving the nice closure and decidability properties of finite automata. Visibly pushdown automata with multiple stacks have been
Benedikt Bollig
doaj +1 more source
Preferred Attribute Elicitation (PAE) in the Sensory Descriptive Analysis of Foods: A Deep Comprehensive Review of the Method Steps, Application, Challenges, and Trends. [PDF]
Compr Rev Food Sci Food SafABSTRACT Descriptive analysis (DA) is the gold standard for sensory profiling due to its robustness and reliability. However, its high cost, time demand, and labor intensity limit routine applications in the food industry. Rapid Sensory Profiling Techniques (RSPTs) have emerged as faster, less resource‐intensive alternatives to address these challenges.
da Silva IBG +5 more
europepmc +2 more sources
Complete Axiomatizations of Fragments of Monadic Second-Order Logic on Finite Trees [PDF]
Logical Methods in Computer Science, 2012 We consider a specific class of tree structures that can represent basic structures in linguistics and computer science such as XML documents, parse trees, and treebanks, namely, finite node-labeled sibling-ordered trees.
Amélie Gheerbrant, Balder ten Cate
doaj +1 more source
The monadic second-order logic of graphs XVI : Canonical graph decompositions [PDF]
Logical Methods in Computer Science, 2006 This article establishes that the split decomposition of graphs introduced by Cunnigham, is definable in Monadic Second-Order Logic.This result is actually an instance of a more general result covering canonical graph decompositions like the modular ...
Bruno Courcelle
doaj +1 more source
Monadic second-order definable graph orderings [PDF]
Logical Methods in Computer Science, 2014 We study the question of whether, for a given class of finite graphs, one can define, for each graph of the class, a linear ordering in monadic second-order logic, possibly with the help of monadic parameters.
Achim Blumensath, Bruno Courcelle
doaj +1 more source