Zobrazeno 1 - 10
of 65
pro vyhledávání: '"Reghizzi, Stefano Crespi"'
We propose different ways of lifting the notion of Dyck language from words to 2-dimensional (2D) pictures, by means of new definitions of increasing comprehensiveness. Two of the proposals are based on alternative definitions of a Dyck language, whi
Externí odkaz:
http://arxiv.org/abs/2307.16522
A recognizable picture language is defined as the projection of a local picture language defined by a set of two-by-two tiles, i.e. by a strictly-locally-testable (SLT) language of order 2. The family of recognizable picture languages is also defined
Externí odkaz:
http://arxiv.org/abs/2206.05208
Publikováno v:
Logical Methods in Computer Science, Volume 19, Issue 4 (November 22, 2023) lmcs:9684
A classic result in formal language theory is the equivalence among non-counting, or aperiodic, regular languages, and languages defined through star-free regular expressions, or first-order logic. Past attempts to extend this result beyond the realm
Externí odkaz:
http://arxiv.org/abs/2006.01236
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
The memory of a deque (double ended queue) automaton is more general than a queue or two stacks; to avoid overgeneralization, we consider quasi-real-time operation. Normal forms of such automata are given. Deque languages form an AFL but not a full o
Externí odkaz:
http://arxiv.org/abs/1806.06562
The famous theorem by Chomsky and Sch\"utzenberger (CST) says that every context-free language $L$ over an alphabet $\Sigma$ is representable as $h(D \cap R)$, where $D$ is a Dyck language over a set $\Omega$ of brackets, $R$ is a local language and
Externí odkaz:
http://arxiv.org/abs/1805.04003
Publikováno v:
EPTCS 252, 2017, pp. 86-100
Floyd's Operator Precedence (OP) languages are a deterministic context-free family having many desirable properties. They are locally and parallely parsable, and languages having a compatible structure are closed under Boolean operations, concatenati
Externí odkaz:
http://arxiv.org/abs/1705.09093
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Publikováno v:
EPTCS 151, 2014, pp. 216-230
Commutative languages with the semilinear property (SLIP) can be naturally recognized by real-time NLOG-SPACE multi-counter machines. We show that unions and concatenations of such languages can be similarly recognized, relying on -- and further deve
Externí odkaz:
http://arxiv.org/abs/1405.5604
This paper has the goals (1) of unifying top-down parsing with shift-reduce parsing to yield a single simple and consistent framework, and (2) of producing provably correct parsing methods, deterministic as well as tabular ones, for extended context-
Externí odkaz:
http://arxiv.org/abs/1309.7584