Results 1 to 10 of about 721,848 (214)
A non-regular language of infinite trees that is recognizable by a sort-wise finite algebra [PDF]
Logical Methods in Computer Science, 2019 $\omega$-clones are multi-sorted structures that naturally emerge as algebras for infinite trees, just as $\omega$-semigroups are convenient algebras for infinite words.
Mikołaj Bojańczyk, Bartek Klin
doaj +1 more source
The Church Synthesis Problem with Parameters [PDF]
Logical Methods in Computer Science, 2007 For a two-variable formula ψ(X,Y) of Monadic Logic of Order (MLO) the Church Synthesis Problem concerns the existence and construction of an operator Y=F(X) such that ψ(X,F(X)) is universally valid over Nat.
Alexander Rabinovich
doaj +1 more source
Automata with Nested Pebbles Capture First-Order Logic with Transitive Closure [PDF]
Logical Methods in Computer Science, 2007 String languages recognizable in (deterministic) log-space are characterized either by two-way (deterministic) multi-head automata, or following Immerman, by first-order logic with (deterministic) transitive closure.
Joost Engelfriet, Hendrik Jan Hoogeboom
doaj +1 more source
On Second-Order Monadic Monoidal and Groupoidal Quantifiers [PDF]
Logical Methods in Computer Science, 2010 We study logics defined in terms of second-order monadic monoidal and groupoidal quantifiers. These are generalized quantifiers defined by monoid and groupoid word-problems, equivalently, by regular and context-free languages.
Juha Kontinen, Heribert Vollmer
doaj +1 more source
Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique [PDF]
Logical Methods in Computer Science, 2008 In this paper, we first introduce a lower bound technique for the state complexity of transformations of automata. Namely we suggest first considering the class of full automata in lower bound analysis, and later reducing the size of the large alphabet ...
Qiqi Yan
doaj +1 more source
Semantics of Typed Lambda-Calculus with Constructors [PDF]
Logical Methods in Computer Science, 2011 We present a Curry-style second-order type system with union and intersection types for the lambda-calculus with constructors of Arbiser, Miquel and Rios, an extension of lambda-calculus with a pattern matching mechanism for variadic constructors.
Barbara Petit
doaj +1 more source
An Application of the Feferman-Vaught Theorem to Automata and Logics for Words over an Infinite Alphabet [PDF]
Logical Methods in Computer Science, 2008 We show that a special case of the Feferman-Vaught composition theorem gives rise to a natural notion of automata for finite words over an infinite alphabet, with good closure and decidability properties, as well as several logical characterizations.
Alexis Bès
doaj +1 more source
Coalgebraic Automata Theory: Basic Results [PDF]
Logical Methods in Computer Science, 2008 We generalize some of the central results in automata theory to the abstraction level of coalgebras and thus lay out the foundations of a universal theory of automata operating on infinite objects. Let F be any set functor that preserves weak pullbacks.
C. Kupke, Y. Venema
doaj +1 more source
Reasoning about Data Repetitions with Counter Systems [PDF]
Logical Methods in Computer Science, 2016 We study linear-time temporal logics interpreted over data words with multiple attributes. We restrict the atomic formulas to equalities of attribute values in successive positions and to repetitions of attribute values in the future or past.
Stephane Demri +2 more
doaj +1 more source
Residuality and Learning for Nondeterministic Nominal Automata [PDF]
Logical Methods in Computer Science, 2022 We are motivated by the following question: which data languages admit an active learning algorithm? This question was left open in previous work by the authors, and is particularly challenging for languages recognised by nondeterministic automata.
Joshua Moerman, Matteo Sammartino
doaj +1 more source