This HTML5 document contains 45 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
n9http://linked.opendata.cz/ontology/domain/vavai/riv/typAkce/
dctermshttp://purl.org/dc/terms/
n8http://localhost/temp/predkladatel/
n14http://purl.org/net/nknouf/ns/bibtex#
n5http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F00216208%3A11320%2F14%3A10289400%21RIV15-MSM-11320___/
n17http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n10http://linked.opendata.cz/resource/domain/vavai/projekt/
n13http://linked.opendata.cz/ontology/domain/vavai/
n19https://schema.org/
shttp://schema.org/
n4http://linked.opendata.cz/ontology/domain/vavai/riv/
skoshttp://www.w3.org/2004/02/skos/core#
n2http://linked.opendata.cz/resource/domain/vavai/vysledek/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n7http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n20http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n21http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n11http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n18http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n6http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n15http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F00216208%3A11320%2F14%3A10289400%21RIV15-MSM-11320___
rdf:type
skos:Concept n13:Vysledek
dcterms:description
The paper provides linguistic observations as a motivation for a formal study of analysis by reduction (AR). It concentrates on a study of the whole mechanism through a class of restarting automata with meta-instructions using pebbles, delete, and shift operations (DS-automata). The complexity of DS-automata is naturally measured by the number of deletions, and the number of word order shifts used in a single meta-instruction. We study reduction languages, backward correctness preserving AR, correctness preserving AR, and show unbounded hierarchies (scales) for various classes of reduction languages by the same finite witness languages. The scales make it possible to estimate relevant complexity issues of analysis by reduction for natural languages. The paper provides linguistic observations as a motivation for a formal study of analysis by reduction (AR). It concentrates on a study of the whole mechanism through a class of restarting automata with meta-instructions using pebbles, delete, and shift operations (DS-automata). The complexity of DS-automata is naturally measured by the number of deletions, and the number of word order shifts used in a single meta-instruction. We study reduction languages, backward correctness preserving AR, correctness preserving AR, and show unbounded hierarchies (scales) for various classes of reduction languages by the same finite witness languages. The scales make it possible to estimate relevant complexity issues of analysis by reduction for natural languages.
dcterms:title
On the Complexity of Reductions by Restarting Automata. On the Complexity of Reductions by Restarting Automata.
skos:prefLabel
On the Complexity of Reductions by Restarting Automata. On the Complexity of Reductions by Restarting Automata.
skos:notation
RIV/00216208:11320/14:10289400!RIV15-MSM-11320___
n4:aktivita
n11:I n11:P
n4:aktivity
I, P(GAP103/10/0783), P(GAP202/10/1333)
n4:dodaniDat
n15:2015
n4:domaciTvurceVysledku
n17:2985640 n17:1248057
n4:druhVysledku
n6:D
n4:duvernostUdaju
n20:S
n4:entitaPredkladatele
n5:predkladatel
n4:idSjednocenehoVysledku
34410
n4:idVysledku
RIV/00216208:11320/14:10289400
n4:jazykVysledku
n21:eng
n4:klicovaSlova
automata; restarting; reductions; complexity
n4:klicoveSlovo
n7:restarting n7:reductions n7:complexity n7:automata
n4:kontrolniKodProRIV
[214AD92B61B9]
n4:mistoKonaniAkce
Kassel, Germany
n4:mistoVydani
Wien, Austria
n4:nazevZdroje
NCMA
n4:obor
n18:IN
n4:pocetDomacichTvurcuVysledku
2
n4:pocetTvurcuVysledku
3
n4:projekt
n10:GAP103%2F10%2F0783 n10:GAP202%2F10%2F1333
n4:rokUplatneniVysledku
n15:2014
n4:tvurceVysledku
Plátek, Martin Lopatková, Markéta Pardubská, Dana
n4:typAkce
n9:WRD
n4:zahajeniAkce
2014-07-28+02:00
s:numberOfPages
16
n14:hasPublisher
Österreichische Computer Gesellschaft
n19:isbn
978-3-85403-304-2
n8:organizacniJednotka
11320