0000000000704172

AUTHOR

Heribert Vollmer

showing 3 related works from this author

The Many Faces of a Translation

2000

First-order translations have recently been characterized as the maps computed by aperiodic single-valued nondeterministic finite transducers (NFTs). It is shown here that this characterization lifts to "V-translations" and "V-single-valued-NFTs", where V is an arbitrary monoid pseudovariety. More strikingly, 2-way V-machines are introduced, and the following three models are shown exactly equivalent to Eilenberg's classical notion of a bimachine when V is a group variety or when V is the variety of aperiodic monoids: V-translations, V-single-valued-NFTs and 2-way V-transducers.

MonoidGroup (mathematics)0102 computer and information sciences02 engineering and technologyCharacterization (mathematics)Translation (geometry)01 natural sciencesCombinatoricsNondeterministic algorithmRegular language010201 computation theory & mathematicsAperiodic graph0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processingVariety (universal algebra)Mathematics
researchProduct

The Descriptive Complexity Approach to LOGCFL

1999

Building upon the known generalized-quantifier-based firstorder characterization of LOGCFL, we lay the groundwork for a deeper investigation. Specifically, we examine subclasses of LOGCFL arising from varying the arity and nesting of groupoidal quantifiers. Our work extends the elaborate theory relating monoidal quantifiers to NC1 and its subclasses. In the absence of the BIT predicate, we resolve the main issues: we show in particular that no single outermost unary groupoidal quantifier with FO can capture all the context-free languages, and we obtain the surprising result that a variant of Greibach's "hardest contextfree language" is LOGCFL-complete under quantifier-free BIT-free interpre…

Discrete mathematicsUnary operationComputer science0102 computer and information sciences02 engineering and technologyComputer Science::Computational ComplexityArityDescriptive complexity theory01 natural sciencesNondeterministic algorithm010201 computation theory & mathematicsDeterministic automatonBIT predicate0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processingNondeterministic finite automatonLOGCFL
researchProduct

The Descriptive Complexity Approach to LOGCFL

1998

Building upon the known generalized-quantifier-based first-order characterization of LOGCFL, we lay the groundwork for a deeper investigation. Specifically, we examine subclasses of LOGCFL arising from varying the arity and nesting of groupoidal quantifiers. Our work extends the elaborate theory relating monoidal quantifiers to NC1 and its subclasses. In the absence of the BIT predicate, we resolve the main issues: we show in particular that no single outermost unary groupoidal quantifier with FO can capture all the context-free languages, and we obtain the surprising result that a variant of Greibach's ``hardest context-free language'' is LOGCFL-complete under quantifier-free BIT-free proj…

FOS: Computer and information sciencesFinite model theoryUnary operationComputer Networks and Communicationsautomata and formal languages0102 computer and information sciencesComputational Complexity (cs.CC)Computer Science::Computational ComplexityArityDescriptive complexity theory01 natural sciencesTheoretical Computer ScienceComputer Science::Logic in Computer ScienceNondeterministic finite automaton0101 mathematicsLOGCFLMathematicsDiscrete mathematicscomputational complexityApplied Mathematics010102 general mathematicsdescriptive complexityNondeterministic algorithmComputer Science - Computational Complexityfinite model theoryQuantifier (logic)Computational Theory and Mathematics010201 computation theory & mathematicsF.1.3Journal of Computer and System Sciences
researchProduct