Results 21 to 30 of about 25,771 (294)
Ambiguity Hierarchy of Regular Infinite Tree Languages [PDF]
Logical Methods in Computer Science, 2021 An automaton is unambiguous if for every input it has at most one accepting computation. An automaton is k-ambiguous (for k > 0) if for every input it has at most k accepting computations. An automaton is boundedly ambiguous if it is k-ambiguous for some
Alexander Rabinovich, Doron Tiferet
doaj +1 more source
Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages [PDF]
Logical Methods in Computer Science, 2023 A classic result in formal language theory is the equivalence among non-counting, or aperiodic, regular languages, and languages defined through star-free regular expressions, or first-order logic.
Dino Mandrioli +2 more
doaj +1 more source
Phylogenetic trees: Grammar versus vocabulary
Russian Journal of Linguistics, 2022 Traditionally, genealogical relationships between languages are established on the basis of phonetic and lexical data. The question whether genealogical relationships among languages can be defined based on grammatical data remains unanswered.
Vladimir N. Polyakov +2 more
doaj +1 more source
E-unification by means of tree tuple synchronized grammars [PDF]
Discrete Mathematics & Theoretical Computer Science, 1997 The goal of this paper is both to give an E-unification procedure that always terminates, and to decide unifiability. For this, we assume that the equational theory is specified by a confluent and constructor-based rewrite system, and that four ...
Sébastien Limet, Pierre Réty
doaj +1 more source
Regular matching problems for infinite trees [PDF]
Logical Methods in Computer Science, 2022 We study the matching problem of regular tree languages, that is, "$\exists \sigma:\sigma(L)\subseteq R$?" where $L,R$ are regular tree languages over the union of finite ranked alphabets $\Sigma$ and $\mathcal{X}$ where $\mathcal{X}$ is an alphabet of ...
Carlos Camino +4 more
doaj +1 more source
A Unified Framework to Compute over Tree Synchronized Grammars and Primal Grammars [PDF]
Discrete Mathematics & Theoretical Computer Science, 2002 Tree languages are powerful tools for the representation and schematization of infinite sets of terms for various purposes (unification theory, verification and specification ...).
Frédéric Saubion, Igor Stéphan
doaj +3 more sources
Operational State Complexity of Deterministic Unranked Tree Automata [PDF]
Electronic Proceedings in Theoretical Computer Science, 2010 We consider the state complexity of basic operations on tree languages recognized by deterministic unranked tree automata. For the operations of union and intersection the upper and lower bounds of both weakly and strongly deterministic tree automata are
Xiaoxue Piao, Kai Salomaa
doaj +1 more source
Language Trees and Zipping [PDF]
Physical Review Letters, 2002 In this letter we present a very general method to extract information from a generic string of characters, e.g. a text, a DNA sequence or a time series. Based on data-compression techniques, its key point is the computation of a suitable measure of the remoteness of two bodies of knowledge.
BENEDETTO, Dario +2 more
openaire +4 more sources
Tree Languages Defined in First-Order Logic with One Quantifier Alternation [PDF]
Logical Methods in Computer Science, 2010 We study tree languages that can be defined in \Delta_2 . These are tree languages definable by a first-order formula whose quantifier prefix is forall exists, and simultaneously by a first-order formula whose quantifier prefix is .
Mikolaj Bojanczyk, Luc Segoufin
doaj +1 more source
The Wadge Hierarchy of Deterministic Tree Languages [PDF]
Logical Methods in Computer Science, 2008 We provide a complete description of the Wadge hierarchy for deterministically recognisable sets of infinite trees. In particular we give an elementary procedure to decide if one deterministic tree language is continuously reducible to another.
Filip Murlak
doaj +1 more source