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

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

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
n5http://localhost/temp/predkladatel/
n21http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n16http://linked.opendata.cz/resource/domain/vavai/projekt/
n8http://linked.opendata.cz/resource/domain/vavai/subjekt/
n7http://linked.opendata.cz/ontology/domain/vavai/
shttp://schema.org/
skoshttp://www.w3.org/2004/02/skos/core#
rdfshttp://www.w3.org/2000/01/rdf-schema#
n20http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F61989100%3A27240%2F13%3A86088970%21RIV14-GA0-27240___/
n3http://linked.opendata.cz/ontology/domain/vavai/riv/
n15http://bibframe.org/vocab/
n2http://linked.opendata.cz/resource/domain/vavai/vysledek/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n10http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n17http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n11http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n4http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n14http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n12http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n13http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F61989100%3A27240%2F13%3A86088970%21RIV14-GA0-27240___
rdf:type
n7:Vysledek skos:Concept
rdfs:seeAlso
http://www.cs.vsb.cz/sawa/papers/fi2013.pdf
dcterms:description
In languages over a unary alphabet, i.e., an alphabet with only one letter, words can be identified with their lengths. It is well known that each regular language over a unary alphabet can be represented as the union of a finite number of arithmetic progressions. Given a nondeterministic finite automaton (NFA) working over a unary alphabet (a unary NFA), the arithmetic progressions representing the language accepted by the automaton can be easily computed by the determinization of the given NFA. However, the number of the arithmetic progressions computed in this way can be exponential with respect to the size of the original automaton. Chrobak (1986) has shown that in fact O(n^2) arithmetic progressions are sufficient for the representation of the language accepted by a unary NFA with n states, and Martinez (2002) has shown how these progressions can be computed in polynomial time. Recently, To (2009) has pointed out that Chrobak's construction and Martinez's algorithm, which is based on it, contain a subtle error and has shown how to correct this error. Geffert (2007) presented an alternative proof of Chrobak's result, also improving some of the bounds. In this paper, a new simpler and more efficient algorithm for the same problem is presented, using some ideas from Geffert (2007). The time complexity of the presented algorithm is O(n^2(n+m)) and its space complexity is O(n+m), where n is the number of states and m the number of transitions of a given unary NFA. In languages over a unary alphabet, i.e., an alphabet with only one letter, words can be identified with their lengths. It is well known that each regular language over a unary alphabet can be represented as the union of a finite number of arithmetic progressions. Given a nondeterministic finite automaton (NFA) working over a unary alphabet (a unary NFA), the arithmetic progressions representing the language accepted by the automaton can be easily computed by the determinization of the given NFA. However, the number of the arithmetic progressions computed in this way can be exponential with respect to the size of the original automaton. Chrobak (1986) has shown that in fact O(n^2) arithmetic progressions are sufficient for the representation of the language accepted by a unary NFA with n states, and Martinez (2002) has shown how these progressions can be computed in polynomial time. Recently, To (2009) has pointed out that Chrobak's construction and Martinez's algorithm, which is based on it, contain a subtle error and has shown how to correct this error. Geffert (2007) presented an alternative proof of Chrobak's result, also improving some of the bounds. In this paper, a new simpler and more efficient algorithm for the same problem is presented, using some ideas from Geffert (2007). The time complexity of the presented algorithm is O(n^2(n+m)) and its space complexity is O(n+m), where n is the number of states and m the number of transitions of a given unary NFA.
dcterms:title
Efficient Construction of Semilinear Representations of Languages Accepted by Unary Nondeterministic Finite Automata Efficient Construction of Semilinear Representations of Languages Accepted by Unary Nondeterministic Finite Automata
skos:prefLabel
Efficient Construction of Semilinear Representations of Languages Accepted by Unary Nondeterministic Finite Automata Efficient Construction of Semilinear Representations of Languages Accepted by Unary Nondeterministic Finite Automata
skos:notation
RIV/61989100:27240/13:86088970!RIV14-GA0-27240___
n7:predkladatel
n8:orjk%3A27240
n3:aktivita
n11:P
n3:aktivity
P(GAP202/11/0340)
n3:cisloPeriodika
1
n3:dodaniDat
n13:2014
n3:domaciTvurceVysledku
n21:2066041
n3:druhVysledku
n14:J
n3:duvernostUdaju
n17:S
n3:entitaPredkladatele
n20:predkladatel
n3:idSjednocenehoVysledku
72062
n3:idVysledku
RIV/61989100:27240/13:86088970
n3:jazykVysledku
n4:eng
n3:klicovaSlova
efficient algorithms; arithmetic progressions; unary languages; automata theory
n3:klicoveSlovo
n10:unary%20languages n10:automata%20theory n10:arithmetic%20progressions n10:efficient%20algorithms
n3:kodStatuVydavatele
NL - Nizozemsko
n3:kontrolniKodProRIV
[B38ACE082A05]
n3:nazevZdroje
Fundamenta Informaticae
n3:obor
n12:IN
n3:pocetDomacichTvurcuVysledku
1
n3:pocetTvurcuVysledku
1
n3:projekt
n16:GAP202%2F11%2F0340
n3:rokUplatneniVysledku
n13:2013
n3:svazekPeriodika
123
n3:tvurceVysledku
Sawa, Zdeněk
n3:wos
000317267500007
s:issn
0169-2968
s:numberOfPages
10
n15:doi
10.3233/FI-2013-802
n5:organizacniJednotka
27240