About: Decidable Synthesis of Programs with Uninterpreted Functions

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Decidable Synthesis of Programs with Uninterpreted Functions Goto Sponge NotDistinct Permalink

An Entity of Type : schema:ScholarlyArticle, within Data Space : covidontheweb.inria.fr associated with source document(s)

Attributes	Values
type	Academic Article research paper schema:ScholarlyArticle
isDefinedBy	Covid-on-the-Web dataset
title	Decidable Synthesis of Programs with Uninterpreted Functions
Creator	Krogmeier, Paul Mathur, Umang Murali, Adithya Viswanathan, Mahesh Madhusudan, P
source	PMC
abstract	We identify a decidable synthesis problem for a class of programs of unbounded size with conditionals and iteration that work over infinite data domains. The programs in our class use uninterpreted functions and relations, and abide by a restriction called coherence that was recently identified to yield decidable verification. We formulate a powerful grammar-restricted (syntax-guided) synthesis problem for coherent uninterpreted programs, and we show the problem to be decidable, identify its precise complexity, and also study several variants of the problem.
has issue date	2020-06-16(xsd:dateTime)
bibo:doi	10.1007/978-3-030-53291-8_32
has license	cc-by
sha1sum (hex)	078aed38940d612394118ee217ed1ff2d991a3e8
schema:url	https://doi.org/10.1007/978-3-030-53291-8_32
resource representing a document's title	Decidable Synthesis of Programs with Uninterpreted Functions
has PubMed Central identifier	PMC7363337
schema:publication	Computer Aided Verification
resource representing a document's body	covid:078aed38940d612394118ee217ed1ff2d991a3e8#body_text
is schema:about of	named entity 'COHERENCE' named entity 'DATA' named entity 'VERIFICATION' named entity 'YIELD' named entity 'RESTRICTION' named entity 'non-recursive' named entity 'parent node' named entity 'doubly exponential' named entity 'time bounds' named entity 'problem is undecidable' named entity 'recursion' named entity 'transition systems' named entity 'finite set' named entity 'left child' named entity 'automaton' named entity 'finite alphabet' named entity 'schema' named entity '5.5' named entity 'algorithm' named entity 'program synthesis' named entity 'program correctness' named entity 'data model' named entity 'Boolean' named entity 'logic' named entity 'linear arithmetic' named entity 'decidability' named entity 'problem is undecidable' named entity 'decidable' named entity 'recursive' named entity 'satisfiable' named entity 'decidable' named entity 'natural class' named entity 'top-down tree automaton' named entity 'automaton' named entity 'Boolean' named entity 'decidable' named entity 'entail' named entity 'lower bound' named entity 'decidable' named entity 'program synthesis' named entity 'pushdown automaton' named entity 'automata' named entity 'data domain' named entity 'recursive' named entity 'program synthesis' named entity 'regular language' named entity 'deterministic automata' named entity 'automaton' named entity 'modulo' named entity 'EXPTIME' named entity 'conditionals' named entity 'Boolean' named entity 'exponential space' named entity 'Finite-state' named entity 'program synthesis' named entity 'schema' named entity 'realizability' named entity 'memoizing' named entity 'commutativity' named entity 'tree automaton' named entity 'Boolean' named entity 'PExec' named entity 'program synthesis' named entity 'tree automata' named entity 'child node' named entity 'nondeterministically' named entity 'tree automaton' named entity 'lower bound' named entity 'linked list' named entity 'left child' named entity 'tree automaton' named entity 'recursive' named entity 'decidability' named entity 'Boolean variable' named entity 'polynomial' named entity 'data model' named entity 'automata' named entity 'decidability' named entity 'decidability'

Faceted Search & Find service v1.13.91 as of Mar 24 2020

Alternative Linked Data Documents: Sponger | ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software