In 1970's, Nivat studied recursive program schemes (a.k.a order-1 higher-order recursion schemes in modern terminology), first-order tree grammars for generating possibly infinite trees. We consider ...the inclusion problem between the frontier language of a non-deterministic recursive program scheme (equivalently, an order-2 word language or indexed language) and the Dyck language, and prove that it is undecidable by a reduction from the undecidability of Hilbert's 10th problem. Essentially the same result has recently been proved by Uezato and Minamide, but our proof is arguably more direct, demonstrating the expressive power of higher-order grammars.
Craig interpolation is an active research topic and has become a powerful technique in verification. We present SMTInterpol, an interpolating SMT solver for the quantifier-free fragment of the ...combination of the theory of uninterpreted functions and the theory of linear arithmetic over integers and reals. SMTInterpol is SMTLIB 2 compliant and available under an open source software license (LGPL v3).
Synthesizing relational queries from data is challenging in the presence of recursion and invented predicates. We propose a fully automated approach to synthesize such queries. Our approach comprises ...of two steps: it first synthesizes a non-recursive query consistent with the given data, and then identifies recursion schemes in it and thereby generalizes to arbitrary data. This generalization is achieved by an iterative predicate unification procedure which exploits the notion of data provenance to accelerate convergence. In each iteration of the procedure, a constraint solver proposes a candidate query, and a query evaluator checks if the proposed program is consistent with the given data. The data provenance for a failed query allows us to construct additional constraints for the constraint solver and refine the search. We have implemented our approach in a tool named Mobius. On a suite of 21 challenging recursive query synthesis tasks, Mobius outperforms three state-of-the-art baselines Gensynth, ILASP, and Popper, both in terms of runtime and accuracy. We also demonstrate that the synthesized queries generalize well to unseen data.
This article analyzes stem allomorphy in Serbo-Croatian neuter noun inflection as morphological epenthesis. I demonstrate that consonant insertion in the inflection of Serbo-Croatian neuter nouns is ...a predictable, morphologically conditioned process, rather than an artifact of listed stem allomorphy. Furthermore, the process is not phonologically optimizing, and does not depend on phonological conditions such as vowel hiatus or illicit phonotactic structure. The present analysis includes the process in a wider, algorithmic interpretation of nominal inflection as logical transductions on strings, using Boolean Monadic Recursive Schemes (BMRSs).
BMRSs are appropriate for modeling morphological processes, as they can intensionally represent morphological substance and generalizations, much like theories of realizational morphology do, while retaining the computationally restrictive nature of such processes. A logical description is therefore offered of Serbo-Croatian neuter noun inflection, including the processes of stem-final consonant insertion and suffix-initial vowel fronting. The work presented here bears wider implications about the nature of morphophonological processes, and the interfaces of morphology with phonology and syntax.
This is a corrigendum for our paper S. Milius, L.S. Moss, The category theoretic solution of recursive program schemes, Theoret. Comput. Sci. 366 (2006) 3–59. The main results are correct, but we ...offer some changes to the definitions and proofs concerning interpreted recursive program schemes.
On second-order iterative monads Adámek, Jiří; Milius, Stefan; Velebil, Jiří
Theoretical computer science,
09/2011, Letnik:
412, Številka:
38
Journal Article
Recenzirano
Odprti dostop
B. Courcelle studied algebraic trees as precisely the solutions of all recursive program schemes for a given signature in Set. He proved that the corresponding monad is iterative. We generalize this ...to recursive program schemes over a given finitary endofunctor H of a “suitable” category. A monad is called second-order iterative if every guarded recursive program scheme has a unique solution in it. We construct two second-order iterative monads: one, called the second-order rational monad, SH, is proved to be the initial second-order iterative monad. The other one, called the context-free monad, CH, is a quotient of SH and in the original case of a polynomial endofunctor H of Set we prove that CH is the monad studied by B. Courcelle. The question whether these two monads are equal is left open.
PDF
