Results 51 to 60 of about 48,609 (342)
FO2(<,+1,~) on data trees, data tree automata and branching vector addition systems [PDF]
Logical Methods in Computer Science, 2016 A data tree is an unranked ordered tree where each node carries a label from a finite alphabet and a datum from some infinite domain. We consider the two variable first order logic FO2(
Florent Jacquemard +2 more
doaj +1 more source
Minimality Notions via Factorization Systems and Examples [PDF]
Logical Methods in Computer Science, 2022 For the minimization of state-based systems (i.e. the reduction of the number of states while retaining the system's semantics), there are two obvious aspects: removing unnecessary states of the system and merging redundant states in the system.
Thorsten Wißmann
doaj +1 more source
Complexity of Problems of Commutative Grammars [PDF]
Logical Methods in Computer Science, 2015 We consider commutative regular and context-free grammars, or, in other words, Parikh images of regular and context-free languages. By using linear algebra and a branching analog of the classic Euler theorem, we show that, under an assumption that the ...
Eryk Kopczynski
doaj +1 more source
Determinisability of register and timed automata [PDF]
Logical Methods in Computer Science, 2022 The deterministic membership problem for timed automata asks whether the timed language given by a nondeterministic timed automaton can be recognised by a deterministic timed automaton.
Lorenzo Clemente +2 more
doaj +1 more source
Asynchronous wreath product and cascade decompositions for concurrent behaviours [PDF]
Logical Methods in Computer Science, 2022 We develop new algebraic tools to reason about concurrent behaviours modelled as languages of Mazurkiewicz traces and asynchronous automata. These tools reflect the distributed nature of traces and the underlying causality and concurrency between events,
Bharat Adsul +3 more
doaj +1 more source
Satisfiability Games for Branching-Time Logics [PDF]
, 2013 The satisfiability problem for branching-time temporal logics like CTL*, CTL and CTL+ has important applications in program specification and verification. Their computational complexities are known: CTL* and CTL+ are complete for doubly exponential time,
Friedmann, Oliver +2 more
core +2 more sources
Weakly-Unambiguous Parikh Automata and Their Link to Holonomic Series [PDF]
International Colloquium on Automata, Languages and ProgrammingWe investigate the connection between properties of formal languages and properties of their generating series, with a focus on the class of holonomic power series.
Alin Bostan +3 more
semanticscholar +1 more source
Completeness Theorems for Kleene algebra with tests and top [PDF]
Logical Methods in Computer ScienceWe prove two completeness results for Kleene algebra with tests and a top element, with respect to guarded string languages and binary relations. While the equational theories of those two classes of models coincide over the signature of Kleene algebra ...
Damien Pous, Jana Wagemaker
doaj +1 more source
Logical Methods in Computer Science, 2020 We introduce a class of algebras that can be used as recognisers for regular tree languages. We show that it is the only such class that forms a pseudo-variety and we prove the existence of syntactic algebras.
Achim Blumensath
doaj +1 more source
Structural Reductions and Stutter Sensitive Properties [PDF]
Logical Methods in Computer ScienceVerification of properties expressed as $\omega$-regular languages such as LTL can benefit hugely from stutter insensitivity, using a diverse set of reduction strategies.
Emmanuel Paviot-Adet +3 more
doaj +1 more source