About: On Biautomata

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

About: On Biautomata Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
Description	We initiate the theory and applications of biautomata. A biautomaton can read a word alternately from the left and from the right. We assign to each regular language L its canonical biautomaton. This structure plays, among all biautomata recognizing the language L, the same role as the minimal deterministic automaton has among all deterministic automata recognizing the language L. We expect that from the graph structure of this automaton one could decide the membership of a given language for certain significant classes of languages. We present the first two results of this kind: namely, a language L is piecewise testable if and only if the canonical biautomaton of L is acyclic. From this result Simon’s famous characterization of piecewise testable languages easily follows. The second class of languages characterizable by the graph structure of their biautomata are prefix-suffix testable languages. We initiate the theory and applications of biautomata. A biautomaton can read a word alternately from the left and from the right. We assign to each regular language L its canonical biautomaton. This structure plays, among all biautomata recognizing the language L, the same role as the minimal deterministic automaton has among all deterministic automata recognizing the language L. We expect that from the graph structure of this automaton one could decide the membership of a given language for certain significant classes of languages. We present the first two results of this kind: namely, a language L is piecewise testable if and only if the canonical biautomaton of L is acyclic. From this result Simon’s famous characterization of piecewise testable languages easily follows. The second class of languages characterizable by the graph structure of their biautomata are prefix-suffix testable languages. (en)
Title	On Biautomata On Biautomata (en)
skos:prefLabel	On Biautomata On Biautomata (en)
skos:notation	RIV/00216224:14310/12:00057567!RIV13-GA0-14310___
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(GA201/09/1313), Z(MSM0021622409)
http://linked.open...iv/cisloPeriodika	4
http://linked.open...vai/riv/dodaniDat	2013
http://linked.open...aciTvurceVysledku	Polák, Libor Klíma, Ondřej
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Masarykova univerzita / Přírodovědecká fakulta
http://linked.open...dnocenehoVysledku	156184
http://linked.open...ai/riv/idVysledku	RIV/00216224:14310/12:00057567
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Biautomata; piecewise testable languages (en)
http://linked.open.../riv/klicoveSlovo	Biautomata piecewise testable languages
http://linked.open...odStatuVydavatele	FR - Francouzská republika
http://linked.open...ontrolniKodProRIV	[E5C58EC453EB]
http://linked.open...i/riv/nazevZdroje	RAIRO - Theoretical Informatics and Applications
http://linked.open...in/vavai/riv/obor	BA
http://linked.open...ichTvurcuVysledku	2 (xsd:int)
http://linked.open...cetTvurcuVysledku	2 (xsd:int)
http://linked.open...vavai/riv/projekt	Algebraic Methods in Automata and Formal Language Theory II
http://linked.open...UplatneniVysledku	2012
http://linked.open...v/svazekPeriodika	46
http://linked.open...iv/tvurceVysledku	Klíma, Ondřej Polák, Libor
http://linked.open...ain/vavai/riv/wos	000310757900007
http://linked.open...n/vavai/riv/zamer	Matematické struktury a jejich fyzikální aplikace
issn	0988-3754
number of pages	20 (xsd:int)
http://bibframe.org/vocab/doi	10.1051/ita/2012014
http://localhost/t...ganizacniJednotka	14310

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software