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

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

Namespace Prefixes

PrefixIRI
n18http://linked.opendata.cz/ontology/domain/vavai/riv/typAkce/
dctermshttp://purl.org/dc/terms/
n21http://localhost/temp/predkladatel/
n3http://purl.org/net/nknouf/ns/bibtex#
n16http://linked.opendata.cz/resource/domain/vavai/projekt/
n6http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n8http://linked.opendata.cz/resource/domain/vavai/subjekt/
n7http://linked.opendata.cz/ontology/domain/vavai/
n20https://schema.org/
n12http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F00216224%3A14310%2F12%3A00057569%21RIV13-GA0-14310___/
shttp://schema.org/
n5http://linked.opendata.cz/ontology/domain/vavai/riv/
skoshttp://www.w3.org/2004/02/skos/core#
n19http://bibframe.org/vocab/
n2http://linked.opendata.cz/resource/domain/vavai/vysledek/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n11http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n23http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n17http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n15http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n13http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n10http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n14http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F00216224%3A14310%2F12%3A00057569%21RIV13-GA0-14310___
rdf:type
skos:Concept n7:Vysledek
dcterms:description
An effective characterization of piecewise testable languages was given by Simon in 1972. A difficult part of the proof is to show that if L has a J -trivial syntactic monoid M(L) then L is k-piecewise testable for a suitable k. By Simon’s original proof, an appropriate k could be taken as two times the maximal length of a chain of ideals in M(L) . In this paper we improve this estimate of k using the concept of biautomaton: a kind of finite automaton which arbitrarily alternates between reading the input word from the left and from the right. We prove that an appropriate k could be taken as the length of the longest simple path in the canonical biautomaton of L. We also show that this bound is better than the known bounds which use the syntactic monoid of L. An effective characterization of piecewise testable languages was given by Simon in 1972. A difficult part of the proof is to show that if L has a J -trivial syntactic monoid M(L) then L is k-piecewise testable for a suitable k. By Simon’s original proof, an appropriate k could be taken as two times the maximal length of a chain of ideals in M(L) . In this paper we improve this estimate of k using the concept of biautomaton: a kind of finite automaton which arbitrarily alternates between reading the input word from the left and from the right. We prove that an appropriate k could be taken as the length of the longest simple path in the canonical biautomaton of L. We also show that this bound is better than the known bounds which use the syntactic monoid of L.
dcterms:title
Biautomata for k-Piecewise Testable Languages Biautomata for k-Piecewise Testable Languages
skos:prefLabel
Biautomata for k-Piecewise Testable Languages Biautomata for k-Piecewise Testable Languages
skos:notation
RIV/00216224:14310/12:00057569!RIV13-GA0-14310___
n7:predkladatel
n8:orjk%3A14310
n5:aktivita
n17:P
n5:aktivity
P(GBP202/12/G061)
n5:dodaniDat
n14:2013
n5:domaciTvurceVysledku
n6:3023516 n6:4177320
n5:druhVysledku
n13:D
n5:duvernostUdaju
n23:S
n5:entitaPredkladatele
n12:predkladatel
n5:idSjednocenehoVysledku
124896
n5:idVysledku
RIV/00216224:14310/12:00057569
n5:jazykVysledku
n15:eng
n5:klicovaSlova
biautomaty; po částech testovatelné jazyky
n5:klicoveSlovo
n11:po%20%C4%8D%C3%A1stech%20testovateln%C3%A9%20jazyky n11:biautomaty
n5:kontrolniKodProRIV
[B1DFFA968A37]
n5:mistoKonaniAkce
Taipei, Taiwan
n5:mistoVydani
Berlin Heidelberg
n5:nazevZdroje
Developments in Language Theory
n5:obor
n10:BA
n5:pocetDomacichTvurcuVysledku
2
n5:pocetTvurcuVysledku
2
n5:projekt
n16:GBP202%2F12%2FG061
n5:rokUplatneniVysledku
n14:2012
n5:tvurceVysledku
Klíma, Ondřej Polák, Libor
n5:typAkce
n18:WRD
n5:zahajeniAkce
2012-01-01+01:00
s:issn
0302-9743
s:numberOfPages
12
n19:doi
10.1007/978-3-642-31653-1_31
n3:hasPublisher
Springer-Verlag
n20:isbn
9783642316524
n21:organizacniJednotka
14310