About: Pebble-Intervals Automata and FO[Formula: see text] with Two Orders

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

About: Pebble-Intervals Automata and FO[Formula: see text] with Two Orders Goto Sponge NotDistinct Permalink

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

Attributes	Values
type	Academic Article research paper schema:ScholarlyArticle
isDefinedBy	Covid-on-the-Web dataset
title	Pebble-Intervals Automata and FO[Formula: see text] with Two Orders
Creator	Kotek, Tomer Labai, Nadia Ortiz, Magdalena Veith, Helmut
source	PMC
abstract	We introduce a novel automata model, which we call pebble-intervals automata (PIA), and study its power and closure properties. PIAs are tailored for a decidable fragment of FO that is important for reasoning about structures that use data values from infinite domains: the two-variable fragment with one total preorder and its induced successor relation, one linear order, and an arbitrary number of unary relations. We prove that the string projection of every language of data words definable in the logic is accepted by a pebble-intervals automaton [Image: see text], and obtain as a corollary an automata-theoretic proof of the [Formula: see text] upper bound for finite satisfiability due to Schwentick and Zeume.
has issue date	2020-01-07(xsd:dateTime)
bibo:doi	10.1007/978-3-030-40608-0_14
has license	no-cc
sha1sum (hex)	1b5d6bd145818add7c29a9375834be0c2b8093d5
schema:url	https://doi.org/10.1007/978-3-030-40608-0_14
resource representing a document's title	Pebble-Intervals Automata and FO[Formula: see text] with Two Orders
has PubMed Central identifier	PMC7206661
schema:publication	Language and Automata Theory and Applications
resource representing a document's body	covid:1b5d6bd145818add7c29a9375834be0c2b8093d5#body_text
is schema:about of	named entity 'language' named entity 'introduce' named entity 'number' named entity 'total preorder' named entity 'string projection' named entity 'structures' named entity 'ExpSpace' named entity 'automaton' named entity 'string projection' named entity 'automata' named entity 'closure properties' named entity 'upper bound' named entity 'automata' named entity 'decidable' named entity 'data values' named entity 'OBTAIN' named entity 'FRAGMENT OF' named entity 'TOTAL' named entity 'ABOUT' named entity 'AUTOMATON' named entity 'RELATION' named entity 'linear order' named entity 'logic' named entity 'finite satisfiability' named entity 'unary' named entity 'INDUCED' named entity 'CLOSURE' named entity 'FINITE' named entity 'ACCEPTED' named entity 'RELATIONS' named entity 'UPPER BOUND' named entity 'LINEAR' named entity 'USE' named entity 'total preorder' named entity 'PIAs' named entity 'SUCCESSOR' named entity 'INTERVALS' named entity 'INTERVALS' named entity 'PEBBLE' named entity 'automata' named entity 'arbitrary number' named entity 'data words' named entity 'power' named entity 'relation' named entity 'reasoning' named entity 'ExpSpace' named entity 'upper bound' named entity 'model' named entity 'closure properties' named entity 'call' named entity 'unary' named entity 'infinite' named entity 'corollary' named entity 'PIAs' named entity 'fragment' named entity 'logic' named entity 'linear order' named entity 'definable' named entity 'arbitrary' named entity 'accepted' named entity 'values' named entity 'proof' named entity 'data' named entity 'relations' named entity 'satisfiability' named entity 'data' named entity 'domains' named entity 'tailored' named entity 'fragment' named entity 'induced' named entity 'finite' named entity 'NOVEL' named entity 'ITS' named entity 'PROPERTIES' named entity 'LANGUAGE' named entity 'ARBITRARY' named entity 'TAILORED' named entity 'PEBBLE' named entity 'Automata' named entity 'STRUCTURES'

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