Results 31 to 40 of about 721,848 (214)
Initial Semantics for Reduction Rules [PDF]
Logical Methods in Computer Science, 2019 We give an algebraic characterization of the syntax and operational semantics of a class of simply-typed languages, such as the language PCF: we characterize simply-typed syntax with variable binding and equipped with reduction rules via a universal ...
Benedikt Ahrens
doaj +1 more source
Groups with context-free Diophantine problem [PDF]
Groups, Complexity, Cryptology, 2021 We find algebraic conditions on a group equivalent to the position of its Diophantine problem in the Chomsky Hierarchy. In particular, we prove that a finitely generated group has a context-free Diophantine problem if and only if it is finite.
Vladimir Yankovskiy
doaj +1 more source
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
A Faithful Semantics for Generalised Symbolic Trajectory Evaluation [PDF]
Logical Methods in Computer Science, 2009 Generalised Symbolic Trajectory Evaluation (GSTE) is a high-capacity formal verification technique for hardware. GSTE uses abstraction, meaning that details of the circuit behaviour are removed from the circuit model.
Koen Claessen, Jan-Willem Roorda
doaj +1 more source
A decidable characterization of locally testable tree languages [PDF]
Logical Methods in Computer Science, 2011 A regular tree language L is locally testable if membership of a tree in L depends only on the presence or absence of some fix set of neighborhoods in the tree.
Thomas Place, Luc Segoufin
doaj +1 more source
Decision Problems for Subclasses of Rational Relations over Finite and Infinite Words [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 We consider decision problems for relations over finite and infinite words defined by finite automata. We prove that the equivalence problem for binary deterministic rational relations over infinite words is undecidable in contrast to the case of finite ...
Christof Löding, Christopher Spinrath
doaj +1 more source
Pushing for weighted tree automata [PDF]
Logical Methods in Computer Science, 2018 A weight normalization procedure, commonly called pushing, is introduced for weighted tree automata (wta) over commutative semifields. The normalization preserves the recognized weighted tree language even for nondeterministic wta, but it is most useful ...
Thomas Hanneforth +2 more
doaj +1 more source
A Generic Framework for Reasoning about Dynamic Networks of Infinite-State Processes [PDF]
Logical Methods in Computer Science, 2009 We propose a framework for reasoning about unbounded dynamic networks of infinite-state processes. We propose Constrained Petri Nets (CPN) as generic models for these networks.
Ahmed Bouajjani +4 more
doaj +1 more source
Automatic Structures: Richness and Limitations [PDF]
Logical Methods in Computer Science, 2007 We study the existence of automatic presentations for various algebraic structures. An automatic presentation of a structure is a description of the universe of the structure by a regular set of words, and the interpretation of the relations by ...
Bakhadyr Khoussainov +3 more
doaj +1 more source
From Nondeterministic B\"uchi and Streett Automata to Deterministic Parity Automata [PDF]
Logical Methods in Computer Science, 2007 In this paper we revisit Safra's determinization constructions for automata on infinite words. We show how to construct deterministic automata with fewer states and, most importantly, parity acceptance conditions.
Nir Piterman
doaj +1 more source