Results 21 to 30 of about 721,848 (214)
Piecewise testable tree languages [PDF]
Logical Methods in Computer Science, 2012 This paper presents a decidable characterization of tree languages that can be defined by a boolean combination of Sigma_1 sentences. This is a tree extension of the Simon theorem, which says that a string language can be defined by a boolean combination
Mikołaj Bojańczyk +2 more
doaj +1 more source
Logical Methods in Computer Science, 2017 Kleene algebra axioms are complete with respect to both language models and binary relation models. In particular, two regular expressions recognise the same language if and only if they are universally equivalent in the model of binary relations.
Paul Brunet, Damien Pous
doaj +1 more source
Almost Every Simply Typed Lambda-Term Has a Long Beta-Reduction Sequence [PDF]
Logical Methods in Computer Science, 2019 It is well known that the length of a beta-reduction sequence of a simply typed lambda-term of order k can be huge; it is as large as k-fold exponential in the size of the lambda-term in the worst case.
Kazuyuki Asada +3 more
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
On the Expressiveness of the Ambient Logic [PDF]
Logical Methods in Computer Science, 2006 The Ambient Logic (AL) has been proposed for expressing properties of process mobility in the calculus of Mobile Ambients (MA), and as a basis for query languages on semistructured data. In this paper, we study the expressiveness of AL.
Daniel Hirschkoff +2 more
doaj +1 more source
Context-Sensitive Languages, Rational Graphs and Determinism [PDF]
Logical Methods in Computer Science, 2006 We investigate families of infinite automata for context-sensitive languages. An infinite automaton is an infinite labeled graph with two sets of initial and final vertices.
Arnaud Carayol, Antoine Meyer
doaj +1 more source
Expressiveness and Closure Properties for Quantitative Languages [PDF]
Logical Methods in Computer Science, 2010 Weighted automata are nondeterministic automata with numerical weights on transitions. They can define quantitative languages~$L$ that assign to each word~$w$ a real number~$L(w)$.
Krishnendu Chatterjee +2 more
doaj +1 more source
Tameness and the power of programs over monoids in DA [PDF]
Logical Methods in Computer Science, 2022 The program-over-monoid model of computation originates with Barrington's proof that the model captures the complexity class $\mathsf{NC^1}$. Here we make progress in understanding the subtleties of the model.
Nathan Grosshans +2 more
doaj +1 more source
Logic Meets Algebra: the Case of Regular Languages [PDF]
Logical Methods in Computer Science, 2007 The study of finite automata and regular languages is a privileged meeting point of algebra and logic. Since the work of Buchi, regular languages have been classified according to their descriptive complexity, i.e.
Pascal Tesson, Denis Therien
doaj +1 more source
Good-for-games $\omega$-Pushdown Automata [PDF]
Logical Methods in Computer Science, 2023 We introduce good-for-games $\omega$-pushdown automata ($\omega$-GFG-PDA). These are automata whose nondeterminism can be resolved based on the input processed so far.
Karoliina Lehtinen, Martin Zimmermann
doaj +1 more source